what happened when using qsort function?

Question

I'm trying to sort the struct node by variable a, but the result turns out to be wrong.

My result:

{5, 4},  {6, 2},  {7, 3},  {4, 1},  {3, 7},  {1, 3},  {0, 0},

My code:

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int x;
    int y;
} n;

int num = 7;

int compare(const void *ele1, const void *ele2) {
    n *px, *py;
    px = (n *) ele1;
    py = (n *) ele2;
    return px->x < py->x;
}

int main() {
    n node[7] = {
    {4, 1},
    {6, 2},
    {1, 3},
    {5, 4},
    {7, 3},
    {3, 7}
    };
    int i;
    qsort(node, num, sizeof (node[0]), compare);
    for (i = 0; i < num; i++)
        printf("{%d, %d},  ", node[i].x, node[i].y);
    return 0;
}

If I sort only six pairs of elements, then the result is:

{7, 3},  {6, 2},  {5, 4},  {4, 1},  {1, 3},  {0, 0},

which is correct, but when I tried with seven, it shows the results above. Does anyone know why that happens? Thanks!

Answer 1

The result of the comparison function should return a negative number, 0, or a positive number. You are returning only 0 or 1.

Your comparison function should return something like this:

return px->x < py->x ? -1 : px->x == py->x ? 0 : 1;

or terser but a little more opaque:

return px->x - py->x;

See qsort reference. It's technically a C++ reference page, but the explanation is good for C as well.

ADDENDUM

I forgot to explain what happened, sorry! Your comparison function does the following.

• Whenever px->x < py->x, your function returned 1, making it think the px tuple was greater than the py tuple, when in fact is what not. (You probably wanted to return a negative value in this case.)

• Whenever px->x >= py->x, your function returned 0, making qsort think that the two values were equal, when in fact they may or may not have been.

So qsort is just blindly partitioning and swapping elements according to what your comparison function was telling it the order was. As your function was giving back only "equal" (0) or "greater" (1), and never "less", the final result turned out to be rather scrambled.