CODEWITHSUNDEEP
csortingpointersquicksortcomparator
ceferrari
ceferrari

Reputation: 1677

C - Custom QuickSort + Comparator using pointers not working

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.

Upvotes: 2

Views: 611

Answers (3)

mc110
mc110

Reputation: 2833

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

Upvotes: 2

BLUEPIXY
BLUEPIXY

Reputation: 40145

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

Upvotes: 2

CiaPan
CiaPan

Reputation: 9570

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

Upvotes: 0

Related Questions