Learn/C/12. Sorting and searching
Lesson 12 of 15
Sign in

C, lesson 12

Sorting and searching

Sorted data is easier to read and much faster to search. The C standard library gives you one general sorting function, qsort, and one search function, bsearch, both in <stdlib.h>. They work on arrays of any type, which makes them a good first look at how C writes generic code.

qsort

You hand qsort four things: the array, the number of elements, the size of one element, and a comparison function. qsort doesn't know what your elements are; it only shuffles bytes around and asks your function which of two elements should come first.

The comparison function receives two const void * pointers (pointers to "something") and must return:

  • a negative number if the first element should come the second,

2 exercises to try what you just read.

Exercise 1

Leaderboard

Press Ctrl Enter or Check to test your code.

Exercise 2

Price checker

Press Ctrl Enter or Check to test your code.

before
  • a positive number if it should come after,
  • zero if they are equal for sorting purposes.
  • Avoid the shortcut return x - y;. With large values of opposite sign the subtraction overflows, which is undefined behaviour. The (x > y) - (x < y) idiom is safe. For descending order, swap the roles: (x < y) - (x > y).

    Sorting records by several keys

    For an array of structs, compare the most important key first and fall back to the next one only when the first is equal:

    p->score reads a member through a pointer. qsort is not stable: elements that compare equal can end up in any order. If the order of ties matters, add a tie-breaking key as above.

    Binary search

    Looking for a value in an unsorted array means checking every element. In a sorted array you can do much better: look at the middle element, and throw away the half that can't contain the target. Each step halves the remaining range, so a million elements need only about 20 steps.

    bsearch

    bsearch does the same job for any type. It takes a pointer to the key you are looking for and the same kind of comparison function, and returns a pointer to a matching element or a null pointer. The array must be sorted with the same ordering the comparison function uses. The key is always passed as the first argument to the comparison function.

    If several elements match, bsearch may return any of them.

    Further reading

    • cppreference: qsort
    • cppreference: bsearch
    • cppreference: strcmp

    Read a count n (1 to 100), then n lines of name score (name is one word, at most 20 characters). Sort the players by score, highest first; players with the same score are ordered by name in strcmp order. Print the ranking as rank. name score.

    A shop's price list arrives unsorted. Read a count n (1 to 1000), then n lines of code price, where code is a whole number and price is in cents. Codes are unique. Sort the list by code, then read product codes until the input ends and, for each one, print <code>: <dollars>.<cents> or <code>: not found. Use bsearch for the lookups.

    void qsort(void *base, size_t count, size_t size,
               int (*compare)(const void *, const void *));
    int by_value(const void *a, const void *b) {
        int x = *(const int *)a;     // turn "pointer to something" into the int it points at
        int y = *(const int *)b;
        return (x > y) - (x < y);    // -1, 0 or 1
    }
    
    int temps[] = {18, -3, 25, 7};
    qsort(temps, 4, sizeof temps[0], by_value);   // -3 7 18 25
    struct player { char name[20]; int score; };
    
    int by_rank(const void *a, const void *b) {
        const struct player *p = a;
        const struct player *q = b;
        if (p->score != q->score) {
            return (q->score > p->score) - (q->score < p->score);  // higher score first
        }
        return strcmp(p->name, q->name);                           // then A to Z
    }
    int find(const int a[], int n, int target) {
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;   // avoids overflow of lo + hi
            if (a[mid] == target) return mid;
            if (a[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;                          // not found
    }
    int key = 18;
    int *hit = bsearch(&key, temps, 4, sizeof temps[0], by_value);
    if (hit != nullptr) {
        printf("found at index %td\n", hit - temps);
    }
    Input:
    4
    mia 120
    leo 95
    ava 120
    zoe 30
    Output:
    1. ava 120
    2. mia 120
    3. leo 95
    4. zoe 30
    Input:
    3
    502 199
    117 1250
    330 5
    330
    999
    117
    Output:
    330: 0.05
    999: not found
    117: 12.50