Bubble sorting in C

Question

I've been into algorithms lately, so I wanted to apply a simple algorithm using a language of my choice, which was C in this case.

I've implemented the bubblesort algorithm (for strings) in a simple program:

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define NUM_NAMES (5)

void sort(char ** sorted, char ** strs, const size_t size, const bool ascending) { // using the bubble sort algorithm
    sorted[0] = strs[0];
    char ** f = strs;
    for(int u=0; u < size; ++u) {
        for(int i = 0; i < size - 1; ++i) {
            if (strcmp(sorted[i], f[i+1]) <= 0) { // sorted[i] is first
                sorted[i+1] = f[i+1];
            } else { // f[i+1] is first
                char *temp = f[i]; // just in case f == sorted, they'll point to the same thing ..
                sorted[i] = f[i+1];
                sorted[i+1] = temp;
            }
        }
        f = sorted;
    }
    if (!ascending) { // reverse it !
        char *reversed[size]; // temporarily
        int i1 = 0, i2 = size - 1;
        while (i1 < size && i2 >= 0) { // one condition would do. Only to be thread-safe
            reversed[i1] = sorted[i2];
            i1++;i2--;
        }
        for(int i = 0; i < size; ++i)
            sorted[i] = reversed[i]; // putting it to sorted
    }
}

void printNames(char * q, char ** names, int num) {
    printf("\t%s\n", q);
    for(int i = 0; i < num; ++i)
        printf("%d: %s\n", i+1, names[i]);
    for(int i = 0; i < 30; ++i)
        printf("=");
    printf("\n");
}

int main(int argc, char const *argv[])
{
    char * names[] = {
        "This should be Second",
        "This should be First",
        "This should be before the last",
        "Wait .. That's the last!",
        "This should be Third"
    };

    char *names_ordered[NUM_NAMES];
    printNames("Original", names, NUM_NAMES);
    sort(names_ordered, names, NUM_NAMES, true);
    printNames("Ascending", names_ordered, NUM_NAMES);
    sort(names_ordered, names, NUM_NAMES, false);
    printNames("Descending", names_ordered, NUM_NAMES);
    return 0;
}

I want to know if there's a problem with the sort function, especially in the reversing part, because I think that that's not efficient.

Answer 1

Reversing is not very efficient indeed (but who cares about an extra linear pass when bubble sort itself is quadratic?). I would rather account for the requested order during the comparison:

result = strcmp(...);
if (!ascending)
    result = -result;

• Initialization f = strs is very confusing, because later on f is reinitialized to sorted. I'd initialize it to sorted always, as close to use as possible.

Something like

for(int u=0; u < size; ++u) {
    char ** f = sorted;
    for(int i = 0; i < size - 1; ++i) {
        ...
    }
}

• One-character names, especially unmotivated like f, u and q should be avoided. You really have to figure out what the variable is, and name it accordingly.

Answer 2

Small details:

• It's confusing that you define NUM_NAMES as a macro and then names as a variable. Either define two variables or two macros, but keep those two items together.

• If you use const, use it everywhere (printNames too).

Answer 3

Bubble sort is well described at https://en.wikipedia.org/wiki/Bubble_sort. The optimized form remembers the last exchange made and notes that all higher elements are sorted already. Bubble sort is an inefficient amgorithm but easy to implement. At worst it runs in O(n^2). In pseudo code:

sort (A, n)     // bubble sort array A[0..n-1]
int j, k, l;

k= n-1;         // k holds position of last interchange. All higher elements are sorted.
while (k > 0)
{
    l= 0;
    for (j=0; j < k; j++)
    {
        if (A[j] > A[j+1])
        {
            tmp   = A[j];
            A[j]  = A[j+1];
            A[j+1]= tmp;
            l= j;
        }
    }
    k= l;
}

EDIT Applying this to the sort algorithm and making the sort more generic, results in how I would write it:

/* Sort unsorted array 'unsorted' of pointers to objects into a sorted array 'sorted'.
 * 'size' has the number of elements in 'unsorted'. Array 'sorted' is assumed to be large enough
 * to hold the sorted result. The arrays are 'pointers to objects' and the result has only
 * the pointers to the original objects, but now in a sorted order. The objects themselves
 * are not copied. Function 'cmp' provided by the caller compares two objects.
 */
void sort(void **sorted, void **unsorted, const size_t size, const int ascending, int (*cmp)(void *, void *))
{
    size_t i, lastXchg, thisXchg;

    for (i=0; i < size; i++)    // first copy the unsorted array to the result array
        sorted[i]= unsorted[i];

    lastXchg= size-1;           // lastXchg remembers the last exchange; all higher elements are sorted
    while (lastXchg > 0)        // now  bubble sort the result array
    {
        thisXchg= 0;                        // remember the last exchange this round
        for (i=0; i < lastXchg; i++)
        {
            int result= cmp(sorted[i], sorted[i+1]);
            if (( ascending && result > 0)
            ||  (!ascending && result < 0))
            {
                void *tmp= sorted[i];
                sorted[i]= sorted[i+1];
                sorted[i+1]= tmp;
                thisXchg= i;
            }
        }
        lastXchg= thisXchg;
    }
}