qsort array of structs descending order

Question

I have a struct that looks like this

typedef struct id_score{
   int id;
   int score;
} pair;

An array of size 50 holds pointers to these pairs

pair* array[50]

My comparator function looks like this

int struct_cmp(const void *a, const void* b) {
    pair* ia = (pair*)a;
    pair* ib = (pair*)b;
    printf("ia's score: %d ib's score: %d??? \n", ia->score, ib->score);
    return ib->score - ia->score;
}

My qsort function here

size_t arr_len = sizeof(array) / sizeof(pair);
qsort(array, arr_len, sizeof(pair), struct_cmp);

Now my problem is that in the struct_cmp function, my printf shows that the values that I think should be the count in each struct in the array are all interpreted as 0, thus not sorting the array at all. Outside of the function when I print through the array, the struct's have scores that it should have.

Any suggestions?? thank you!

Is not a in a pointer to the element? The array elements are type pair* So pair** ia = (pair**)a;? — chux
– chux, Commented Feb 23, 2017 at 22:19
You're sorting an array of pointers; your comparator is passed a pair of pointers to pointers, not single level pointers. If you were sorting an array of int, your function would be passed two int *. Since you're sorting an array of pair *, your function is passed two pair **. — Jonathan Leffler
– Jonathan Leffler, Commented Feb 23, 2017 at 22:21
Note: When you call qsort(), consider qsort(array, arr_len, sizeof *array, struct_cmp); This is easier to code, review, and maintain than qsort(..., ..., sizeof(pair), ...) — chux
– chux, Commented Feb 23, 2017 at 22:33

StoryTeller - Unslander Monica · Accepted Answer · 2017-02-23 22:23:54Z

5

For one

size_t arr_len = sizeof(array) / sizeof(pair);

The above is wrong, as your array contains pair pointers, and not pairs. Doing it a bit more idiomatically and with less repetition would be:

size_t arr_len = sizeof(array) / sizeof(array[0]);

Another thing to note, is that your comparison function converts to the wrong pointer type, so the behavior of your program is undefined.

Remember that the callback function will receive pointers to array elements, so if the array contains pointers, it should convert the arguments to pointers to pointers:

int struct_cmp(const void *a, const void* b) {
    pair* const * ia = (pair* const *)a;
    pair* const * ib = (pair* const *)b;
    printf("ia's score: %d ib's score: %d??? \n", ia->score, ib->score);
    return (*ib)->score - (*ia)->score;
}

Unlike your original function, I also strove to make it const correct. The compare callback accepts by a pointer to const, so the converted pointer should be to const as well (with const being applied to the element type, which is pair*).

As chux pointed out, as a way to avoid overflow in the subtraction, a major improvement will be to return the following instead:

return ((*ib)->score > (*ia)->score) - ((*ib)->score < (*ia)->score);

Which also has the nice property of always returning -1, 0 or 1 instead of arbitrary numbers.

edited Feb 23, 2017 at 22:23

answered Feb 23, 2017 at 22:17

StoryTeller - Unslander Monica

172k22 gold badges401 silver badges481 bronze badges

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

5 Comments

chux Over a year ago

To avoid overflow in the subtraction, could use (a>b) - (a< b) idiom.

StoryTeller - Unslander Monica Over a year ago

@chux - Added. And thank you for making me aware of the idioms existence :)

chux Over a year ago

My understanding is that compilers look for it too, so a reasonable chance to emit tight code. Yet for me, it plugs a functional hole vs. return a-b. Nice bit about the const correct. LSNED

namesake22 Over a year ago

I guess my biggest error came from return ib->score - ia->score; } ??

StoryTeller - Unslander Monica Over a year ago

@namesake22 The biggest problems IMO were those that are unlikely to break your program immediately. Such as the array size issue. The wrong pointer conversion would have vexed you until you solved it.

Collectives™ on Stack Overflow

qsort array of structs descending order

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related