Skip to content
Tutorials Center
My learning

Topics

Lesson 79 of 135 ยท Standard Library

qsort and bsearch

Sort any array in C with qsort - ints, doubles, strings and structs, with multiple keys - write correct comparator functions, and find elements fast with bsearch.

Sorting is one of the most common jobs in programming, and C's standard library does it for you with qsort, declared in <stdlib.h>. It can sort an array of anything, from ints to strings to structs, because you tell it two things: how big each element is, and how to compare two elements. Its partner bsearch finds an element in a sorted array in a handful of steps, even among millions.

The key skill is writing the comparator function. Get it right and one line sorts your data; get it subtly wrong (the infamous return a - b;) and the sort works in tests and fails on real data. This lesson builds comparators for every common case and shows the traps. You'll use void pointers and function pointers, so review those lessons if the syntax looks unfamiliar.

How qsort works

C
void qsort(void *base, size_t count, size_t size,
           int (*compare)(const void *, const void *));
  • base points to the first element of the array.
  • count is the number of elements, and size is the size of one element in bytes (sizeof array[0]).
  • compare is a function that receives pointers to two elements and returns a negative number if the first should come before the second, zero if they're equal for sorting purposes, and a positive number if the first should come after.

qsort doesn't know your element type; it only moves blocks of size bytes around. Your comparator converts the const void * arguments back into pointers to the real type. Despite the name, the standard doesn't require quicksort or any particular algorithm (real libraries use merge sort, introsort and other variants), so rely only on the documented behavior.

Sorting numbers

C Sorting ints up and down

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The expression (x > y) - (x < y) is the idiomatic three-way comparison: each comparison is 0 or 1, so the result is -1, 0 or 1. To sort in reverse, swap the arguments rather than writing a second comparison.

Why not return a - b?

You'll see return *(int *)a - *(int *)b; in many tutorials. It works for small numbers, but when the values are far apart, the subtraction overflows, which is undefined behavior for signed integers and in practice flips the sign:

C The a - b comparator breaks on big values

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The true difference, 2147483657, doesn't fit in an int, and converted back it becomes -2147483639, which tells qsort that INT_MAX is smaller than -10. (The demo computes the difference in long long and converts it, which is implementation-defined but well-defined in GCC, so the run is predictable. A plain int subtraction would be undefined behavior.) Use the comparison form for every integer type.

For double, the same (x > y) - (x < y) pattern works, with one caveat: if the array can contain NaN, every comparison with NaN is false, the comparator becomes inconsistent, and the result is unpredictable. Remove NaNs first or decide explicitly where they go (for example if (isnan(x)) return isnan(y) ? 0 : 1; to put them last).

Sorting strings

How you sort strings depends on how they're stored, and this is where most beginner bugs live.

For an array of pointers (const char *names[]), each element is a char *, so the comparator receives pointers to pointers. Dereference once to get the strings, then use strcmp:

C Sorting an array of string pointers and a 2D char array

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

strcmp compares character codes, so every uppercase letter (Aโ€“Z are 65โ€“90) sorts before every lowercase one (aโ€“z are 97โ€“122): Apricot Banana apple cherry pear. The case-insensitive comparator fixes that, giving apple Apricot Banana cherry pear. Sorting pointers only moves the pointers; the string literals themselves stay where they are.

For a 2D char array (char cities[][16]), each element is a 16-byte row, qsort moves whole rows, and the comparator receives pointers to the first character of each row, so no extra dereference is needed. Mixing up these two cases is a classic mistake: passing compare_rows to the pointer array would make strcmp read the pointers' bytes as text.

Tip: For real human-language text, strcmp and ASCII tolower aren't enough (think of "รฉ" or "รŸ"). strcoll compares strings by the rules of the current locale after setlocale(LC_COLLATE, ""), and dedicated libraries like ICU handle full Unicode collation.

Sorting structs by one or more keys

Struct comparators look at the fields you care about. For multiple keys, compare the first key and only fall through to the next one if the first is equal:

C Sorting employees by department, then salary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Inside each department, the highest salary comes first, and the two it employees with equal salaries (Kofi and Ravi) and the two sales employees earning 52000 (Ana and Noor) are ordered by name. In C (unlike C++), a const void * converts to const struct employee * without a cast, which keeps comparators short.

Warning: qsort is not stable: elements that compare equal may end up in any order, and that order can change between C libraries. In the second sort above, Ana and Noor both earn the least, so either could be printed as "lowest paid". If equal elements must keep their original order, add a final tie-breaker key (such as an ID or the original index) or write a stable merge sort (Sorting and Searching Algorithms).

A comparator must also be consistent: if it says a < b and b < c, it must say a < c, and comparing the same pair must always give the same answer. Comparators that use random numbers, change global state, or treat NaN carelessly break that rule, and the C standard then gives no guarantees at all about the result.

Searching with bsearch

bsearch performs a binary search on a sorted array: it compares the key with the middle element, throws away the half that can't contain it, and repeats. A million elements need at most 20 comparisons.

C
void *bsearch(const void *key, const void *base, size_t count, size_t size,
              int (*compare)(const void *, const void *));

It returns a pointer to a matching element, or NULL if there is none. Two rules matter:

  1. The array must be sorted with the same ordering the comparator uses. Searching an unsorted array, or one sorted by a different key, silently returns wrong answers.
  2. The comparator's first argument is the key and the second is an array element. They don't need to be the same type, which lets you search structs by just a name or ID.
C Looking up records with bsearch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Subtracting the array's start from the returned pointer gives the element's index; %td prints a ptrdiff_t (Pointer Arithmetic). Japan is found at index 3 because the array is now sorted by code: BR, DE, IN, JP, MX, NG.

If several elements match, bsearch may return any of them, not necessarily the first. And it can't tell you where a missing key would go. For that, write a small lower bound search that returns the index of the first element not less than the key:

C
/* Index of the first element >= key in a sorted int array (count if none). */
size_t lower_bound(const int *values, size_t count, int key)
{
    size_t lo = 0, hi = count;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;   /* avoids overflow of lo + hi */
        if (values[mid] < key) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

This tells you where to insert a new value to keep the array sorted, finds the first of several duplicates, and counts how many values are below a threshold.

Note: There's no standard way to pass extra data (like "sort by this column") into a comparator except through a global variable. POSIX 2024 and glibc offer qsort_r with an extra context argument, and C11's optional Annex K has qsort_s, but their argument orders differ between platforms, so check your system's documentation before using them.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. You sort const char *words[] with qsort. What does the comparator receive?

    qsort always passes pointers to elements. The elements are char pointers, so the arguments are pointers to char pointers.
  2. 2. Why is return *(const int *)a - *(const int *)b; a dangerous comparator?

    For example INT_MAX - (-10) overflows, which is undefined behavior and in practice produces a negative number. (x > y) - (x < y) never overflows.
  3. 3. qsort sorts {"bob", "Alice", "carl"} with strcmp. What is the result?

    strcmp compares character codes, and 'A' (65) is less than 'b' (98) and 'c' (99), so Alice comes first. The problem only appears with mixed case, for example "apple" vs "Banana".
  4. 4. Two employees compare equal in your comparator. After qsort, which comes first?

    The C standard says nothing about the relative order of equal elements. Add another key, like an ID, to make the order fully defined.
  5. 5. You call bsearch on an array that was never sorted. What happens?

    Binary search discards half the array at each step based on the ordering. On unsorted data, it can discard the half that contains the key.

Summary

  • qsort(base, count, size, compare) sorts any array; pass sizeof array[0] as the size.
  • A comparator returns negative, zero or positive. Use (x > y) - (x < y) for numbers, never x - y; swap the arguments to sort in reverse.
  • For an array of char *, the comparator gets pointers to pointers; for a 2D char array, it gets pointers to the rows' characters. Use strcmp, or a case-insensitive or locale-aware comparison when needed.
  • For structs, compare the most important key first and fall through to the next key only on ties.
  • qsort is not stable; add a tie-breaker when the order of equal elements matters, and keep comparators consistent (watch out for NaN).
  • bsearch(key, base, count, size, compare) finds an element in an array sorted with the same order; the comparator's first argument is the key. Write a lower_bound loop to find insertion points.

Next: Useful stdlib.h Functions, where you'll end programs cleanly with exit and atexit, read environment variables and use abs and div.