Step 4 of 6

Sorting with qsort

The standard library's qsort sorts any array: ints, doubles, structs, strings. It can do that because it doesn't compare elements itself. You give it a comparator callback that knows how to compare two elements of your type:

void qsort(void *base, size_t count, size_t size,
           int (*cmp)(const void *a, const void *b));

The comparator gets pointers to two elements, typed as const void * (pointer to "something"), and must return negative if a should come first, positive if b should, and 0 if they're equal. You convert the pointers back to the real type inside.

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

typedef struct {
    char name[12];
    double price;
} Item;

static int by_price(const void *pa, const void *pb) {
    const Item *a = pa, *b = pb;
    if (a->price != b->price) {
        return (a->price > b->price) - (a->price < b->price);
    }
    return strcmp(a->name, b->name);
}

int main(void) {
    Item shop[] = {{"lamp", 20.0}, {"cup", 5.5}, {"book", 20.0}};
    qsort(shop, 3, sizeof shop[0], by_price);
    for (int i = 0; i < 3; i++) printf("%s %.2f\n", shop[i].name, shop[i].price);
    return 0;
}

cup 5.50
book 20.00
lamp 20.00

Writing comparators correctly

• (a > b) - (a < b) gives -1, 0 or 1. The shortcut return a - b; looks tempting for ints but overflows for large values of opposite signs, which is undefined behavior and silently misorders elements.
• For several sort keys, compare the most important first, and only if it's a tie move on to the next (here, name as a tie-breaker). This gives a predictable order. It matters because qsort is not stable: it may put equal elements in any order, so without a tie-breaker, items with the same price could come out differently on different systems.
• For descending order, swap the roles of a and b.

The pointer conversion const Item *a = pa; works without a cast in C, because a void * converts to any object pointer automatically.

Your turn: write a comparator by_score_desc for Player structs: higher score first, and for equal scores, alphabetical by name. Then sort_players calls qsort with it.

Previous: A dispatch table Next: Generic code with void *