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
– CiaPan, Commented Jul 15, 2014 at 14:40
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
– ceferrari, Commented Jul 15, 2014 at 18:43
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, Commented Jul 15, 2014 at 19:29

mc110 · Accepted Answer · 2014-07-15 21:06:58Z

2

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

edited Jul 15, 2014 at 21:06

answered Jul 15, 2014 at 20:24

mc110

2,8415 gold badges22 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

ceferrari Over a year ago

Thanks @mc110 but this won't work. I got a totally random output

mc110 Over a year ago

Apologies - I reduced your previous data set to the minimum for debugging, then got that working,and did not expand back to the full data set!

ceferrari Over a year ago

No problem! Please check my edit on the original post if you can. Ty

ceferrari Over a year ago

It worked!! Thank you @mc110 not only for the answer but for the explanation too

BLUEPIXY · Accepted Answer · 2014-07-15 21:02:53Z

2

the problems of your quickSort function is that it does not consider that there may pivot is replaced.

static void quickSort(player *arr, int left, int right) {
    int m = (left+right)/2;
    player mp = arr[m];//I'll fixed
    int l = left, r = right;
    while (l <= r) {
        while (comp(arr+l, &mp) < 0) l++;
        while (comp(arr+r, &mp) > 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);
}

answered Jul 15, 2014 at 21:02

BLUEPIXY

40.2k7 gold badges37 silver badges73 bronze badges

2 Comments

WhozCraig Over a year ago

Both you and mc110 are correct. I utterly spaced on the pivot choice selection when coding the original algorithm. It was going to be the left-to-right sweep algorithm rather than the squeeze algorithm, and I simply forgot to extract the pivot value to a temporary,or in mc110's case, home from left. Thanks for catching this error.

ceferrari Over a year ago

That fixed it. I already accepeted @mc110 solution as answer but this Ive just tested and this one will work too. Thanks BLUEPIXY

CiaPan · Accepted Answer · 2014-07-15 20:02:09Z

0

Yes, you should worry. Standard string functions expect strings NUL-terminated and scanf stores string in this manner, too. If you enter a string longer than 15 characters, it gets stored in some player structure name member field (say, arr[0].name), but will overflow the name array, and some tail characters together with a terminating NUL (ASCII zero char) get stored outside the name array and outside the arr[0] variable, probably overwriting the next player's total (arr[1].total). Next you store new player's data in arr[1] and some bytes of arr[1] total 'glue' to the initial 16 chars of arr[0].name. That causes some unpredicted differences between 'equal' names. Furthermore during sorting the player structures get swapped and 'the same' name suddenly 'glues' to some new 'tail', resulting in inconsistent comparisions (same data, when moved to a different place, may compare either less or greater than the pivot).

answered Jul 15, 2014 at 20:02

CiaPan

9,5802 gold badges23 silver badges38 bronze badges

1 Comment

ceferrari Over a year ago

Thanks for answering. I got your point but I am sure 16 is enough. The maximum number of characters in name will be 15 and thats why I set it to 16, to include the '\0'.

Collectives™ on Stack Overflow

C - Custom QuickSort + Comparator using pointers not working

3 Answers 3

4 Comments

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related