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];
        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)

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.


3 Answers 3


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.
  • \$\begingroup\$ 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 .. \$\endgroup\$
    – Amr Ayman
    Commented Sep 3, 2014 at 23:39
  • \$\begingroup\$ Also, I tried result = -result and it doesn't seem to work for some reason .. \$\endgroup\$
    – Amr Ayman
    Commented Sep 3, 2014 at 23:42
  • \$\begingroup\$ 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. \$\endgroup\$
    – vnp
    Commented Sep 4, 2014 at 0:07
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Commented Sep 4, 2014 at 4:51
  • \$\begingroup\$ @LokiAstari Even better, you can abort bubble sort at any time if a roughly sorted list is acceptable. \$\endgroup\$
    – aggsol
    Commented Oct 23, 2014 at 13:21

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).


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;
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jul 30, 2015 at 18:54
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Jul 31, 2015 at 10:41
  • \$\begingroup\$ 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? \$\endgroup\$ Commented Jul 31, 2015 at 10:46
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jul 31, 2015 at 11:29
  • \$\begingroup\$ @Ismael-Miguel, I took your comments to heart and attempted to improve my answer. Thanks for the feedback. \$\endgroup\$ Commented Jul 31, 2015 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.