C - Custom QuickSort + Comparator using pointers not working

Question

I am trying to implement a custom quicksort and a custom comparator because i need to sort a struct by two elements (if the first are equal, sort by the second).

I used the following code, which was originally posted at the first answer of: Sorting an array using multiple sort criteria (QuickSort)

typedef struct player {
    int total;
    char name[16];
} player;

void swap(player *p1,player *p2) {
    player tmp = *p2;
    *p2 = *p1;
    *p1 = tmp;
}

int comp(const player *p1,const player *p2) {
    if (p1->total < p2->total) return 1;
    if (p1->total > p2->total) return -1;
    return strcmp(p1->name, p2->name);
}

static void quickSort(player *arr, int left, int right) {
    int m = (left+right)/2;
    int l = left, r = right;
    while (l <= r) {
        while (comp(arr+l, arr+m) < 0) l++;
        while (comp(arr+r, arr+m) > 0) r--;
        if (l <= r) {
            swap(arr+l, arr+r);
            l++; r--;
        }
    }
    if (r > left) quickSort(arr, left, r);
    if (l < right) quickSort(arr, l, right);
}

I cant get this to work. It will succesfully sort by total but fails to sort by name when the two totals are equal.

Yes, Ive tried using this comparator with the standard qsort function and it worked just fine. But using it will be my last alternative.

Any help is appreciated.

Edit:

I am guessing the pivot is the problem. When I add 1 to it the 'name' ordering works fine but a few 'total' elements gets out of order.

Are you sure players' names fit 16-char array and are properly terminated with a zero char within the array? — CiaPan
What do you mean BLUEPIXY? @CiaPan well I am using scanf to read them from stdin. Should I worry about that? They have no spaces or special characters on them, just uppercase or lowercase letters — ceferrari
the problem is with the quickSort routine, as thanks to ceferrari's clarification to my (deleted by me) answer I can verify this does work if calling qsort but not with his quickSort routine. I initially thought the problem was with the comparison function as it order by id descending then name ascending, but ceferrari indicated that was intentional. — mc110

mc110 mc110 · Accepted Answer · 2014-07-15T20:24:12

There are a number of discrepancies between your quicksort algorithm and a standard implementation (see e.g. http://www.codingbot.net/2013/01/quick-sort-algorithm-and-c-code.html), mainly based around edge conditions which is why you've been able to see the problems when you have a number of identical entries in your list to be sorted.

If you change the quickSort routine to this, all should be well - the main differences are:

1) main while loop does not continue with equality condition

2) do not swap if items are at the same index, and do not change our walking pointers after swapping.

3) choose the first item in the list as the pivot each time, and then swap that with one of the items we've walked towards the middle of the list (the right item in this case).

4) after completing the sort either side of the pivot, then search the top and bottom half explicitly (i.e. from start to pivot-1, then pivot+1 to end).

static void quickSort(player *arr, int left, int right) {
  int m = left;
  int l = left, r = right;
  while (l < r) {
    while (comp(arr+l, arr+m) <= 0) l++;
    while (comp(arr+r, arr+m) > 0) r--;

    if (l < r) {
      swap(arr+l, arr+r);
    }
  }
  swap (arr+m, arr+r);

  if (r > left) quickSort(arr, left, r-1);
  if (l < right) quickSort(arr, r+1, right);
}

C - Custom QuickSort + Comparator using pointers not working

3 Answers