Lesson 7 · 7 of 20

qsort and bsearch with comparators · C

Sort an array of structs in C with qsort and a comparison function, then search it with bsearch: a shop's products by price and by code.

C · qsort and bsearch with comparators in DMarlon Studio: the example's code and its output in the terminal

`qsort`, from stdlib.h, sorts any array: it takes the array, the number of elements, the size of each one and a comparator. It has no idea what is inside, which is why the comparator receives two const void * that you cast to the real type, here const Product *.

The comparator returns a negative number if the first goes first, zero if they are equal and a positive one if it goes after. (x > y) - (x < y) gives exactly -1, 0 or 1. The tempting x - y breaks with doubles (converted to int, 0.5 becomes 0) and with very large integers, which overflow.

by_price sorts from cheapest to dearest. For the opposite order, just swap a and b in the comparator.

`bsearch` does a binary search: it looks at the middle and throws away half at each step, so it finds one element among a million in about 20 comparisons. In return, the array must be sorted by the same key you search for, which is why it is sorted again with by_code before searching.

The search key is a Product with only the code filled in. bsearch returns a pointer to the element it found or NULL, as with code 9999.

Code · main.c

#include <stdio.h>#include <stdlib.h>typedef struct { int code; const char *name; double price; } Product;// Comparators get two const void * and return <0, 0 or >0.int by_price(const void *a, const void *b) {    double x = ((const Product *)a)->price, y = ((const Product *)b)->price;    return (x > y) - (x < y);  // no subtraction: it could overflow or truncate}int by_code(const void *a, const void *b) {    int x = ((const Product *)a)->code, y = ((const Product *)b)->code;    return (x > y) - (x < y);}int main(void) {    Product shelf[] = {{3051, "Olive oil", 8.95}, {1007, "Bread", 1.20}, {2210, "Cheese", 6.40},                       {1530, "Milk", 0.99}, {4100, "Coffee", 4.75}};    size_t n = sizeof shelf / sizeof shelf[0];    qsort(shelf, n, sizeof shelf[0], by_price);    printf("By price:\n");    for (size_t i = 0; i < n; i++)        printf("  %4d %-10s %5.2f\n", shelf[i].code, shelf[i].name, shelf[i].price);    // bsearch needs the array sorted by the same key it searches for.    qsort(shelf, n, sizeof shelf[0], by_code);    printf("By code: first %d, last %d\n", shelf[0].code, shelf[n - 1].code);    int wanted[] = {2210, 9999};    for (int w = 0; w < 2; w++) {        Product key = {wanted[w], NULL, 0};        Product *hit = bsearch(&key, shelf, n, sizeof shelf[0], by_code);        printf("Code %d: %s\n", wanted[w], hit ? hit->name : "not found");    }    return 0;}

Output · cc main.c -o main && ./main

By price:
  1530 Milk        0.99
  1007 Bread       1.20
  4100 Coffee      4.75
  2210 Cheese      6.40
  3051 Olive oil   8.95
By code: first 1007, last 4100
Code 2210: Cheese
Code 9999: not found

Key points

qsort(array, n, sizeof array[0], comparator) sorts any type.
The comparator returns <0, 0 or >0; (x > y) - (x < y) is safe.
bsearch needs the array sorted by the same key.
bsearch returns a pointer to the element or NULL.

Exercise

Write by_name using strcmp, sort the shelf by name and look up "Milk" with bsearch.