current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 7 down vote favorite
1

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.

share|improve this question

4 Answers 4

up vote 15 down vote accepted
+50

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.
share|improve this answer
    
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 Sep 3 '14 at 23:39
    
Also, I tried result = -result and it doesn't seem to work for some reason .. –  Amr Ayman Sep 3 '14 at 23:42
    
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. –  vnp Sep 4 '14 at 0:07
2  
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. –  Loki Astari Sep 4 '14 at 4:51
    
@LokiAstari Even better, you can abort bubble sort at any time if a roughly sorted list is acceptable. –  Code Clown Oct 23 '14 at 13:21
up vote 6 down vote

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

share|improve this answer
up vote 0 down vote

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;
    }
}
share|improve this answer
    
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. –  Ismael Miguel Jul 30 at 18:54
    
@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. –  Paul Ogilvie Jul 31 at 10:41
    
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? –  Ismael Miguel Jul 31 at 10:46
    
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 Jul 31 at 11:29
    
@Ismael-Miguel, I took your comments to heart and attempted to improve my answer. Thanks for the feedback. –  Paul Ogilvie Jul 31 at 13:45
up vote -5 down vote

The final sort function:

int sort(char ** sorted, char ** strs, const size_t size, const bool ascending) { // using the bubble sort algorithm
    int result, times;
    bool changed; // boolean to check if a loop makes a change to "sorted"
    sorted[0] = strs[0];
    char ** test; // a pointer to the string array to be arranged
    test = strs; // initialized to strs, only first time to populate "sorted"
    for(times = 0; times < size; ++times) {
        changed = false;
        for(int i = 0; i < size - 1; ++i) {
            result = strcmp(sorted[i], test[i+1]);
            result = ascending ? result : -result;
            if (result <= 0) { // sorted[i] is first
                changed = changed ? true : sorted[i+1] != test[i+1];
                sorted[i+1] = test[i+1];
            } else { // test[i+1] is first
                char *temp = sorted[i]; // just in case test == sorted, they'll point to the same thing. test[i] might not work if test != sorted
                sorted[i] = test[i+1];
                changed = changed ? true : (sorted[i] != test[i+1] || sorted[i+1] != temp);
                sorted[i+1] = temp;
            }
        }
        if (!changed)
            return times+1; // because one was wasted
        times == 0 ? test = sorted : NULL; // "sorted" is to be arranged in "sorted" (itself) several times -- core of the bubble sort algorithm
    }
    return times;
}

I listened to @vpn's advice:

  • I changed f to be test for clarity
  • I added comments to indicate the use of the test pointer
  • I removed the reversing part and just inverted the result of strcmp(), to essentially arrange in descending order.

I also added the changed boolean to detect if any changes were actually made, so that if we have an array of 300 strings (maybe from a database) that was sorted in the first iteration, we don't have to run all again and just waste CPU power and time. The boolean itself, due to the simple structure of the loop, doesn't require complex conditions.

share|improve this answer
7  
It's much more polite to accept vpn's answer. –  JaDogg Sep 29 '14 at 2:07
    
@JaDogg: I'd normally do that, but I recently read a meta post that suggested adding the improved code with reference to the helping answer in a new answer then accepting it. Sorry, if that wasn't good advice. –  Amr Ayman Sep 30 '14 at 18:40
2  
No you have understood it the wrong way. please ask in the chat room about it. –  JaDogg Sep 30 '14 at 18:43
    
Also please see this Meta post : meta.codereview.stackexchange.com/questions/2531/… –  JaDogg Sep 30 '14 at 18:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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