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.

• Amr Ayman: I get all your points, except for the initialization issue. What's wrong with it ? f is the string array to order, and since sorted is empty at first, I can't always make f point to sorted ..
• Amr Ayman: Also, I tried result = -result and it doesn't seem to work for some reason ..
• vnp: It is confusing: glancing at the code I see that f sometimes points into strs, and sometimes into sorted, and I need a mental effort to realize that pointing into strs is bogus. Now, sorted is not empty. You just have sorted[0] = strs[0]. Regarding result tweak not working I have no say. Some debugging is in order.
• Loki Astari: Best case Bubble is linear. So still a useful function if you know your data is nearly or probably already sorted. Or when the data set is small bubble is efficient because of the low overhead.
• aggsol: @LokiAstari Even better, you can abort bubble sort at any time if a roughly sorted list is acceptable.

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;
 }
}

• Ismael Miguel: Honestly, I don't think this is a good answer. You make the same mistakes as the O.P. did, regarding short and cryptic variable names, and you don't even explain what you have done to improve the code.
• Paul Ogilvie: @Ismael-Miguel, algorithms may require explanation very much beyond comments in code. Thereto papers are written. Further, short variable names, in cases, bring more clarity of the algorithm's steps than long variabe names. I do use the convenion though, that such algorithms should fit on one screen to give the reader the overview. Names like i and j are not cryptic; they are clearly integer indexes. The code improvement is showing the O.P. how to remember the last interchange (k) as all higher elements are already sorted.
• Ismael Miguel: Instead of l, try last. Instead of A, try numbers or something. Instead of j, try i (since it is in a for loop). Instead of k try .... I don't know, what does k do? "k holds position of last interchange. All higher elements are sorted." --> Is that the last sorted index?
• Paul Ogilvie: Yes, I could have started the variables at i. A is a generic name standing for Array. For details of the algorithm, see en.wikipedia.org/wiki/Bubble_sort, under optimized.
• Paul Ogilvie: @Ismael-Miguel, I took your comments to heart and attempted to improve my answer. Thanks for the feedback.