Searching and sorting by a comparison rule
Connect qsort and bsearch to arrays, element sizes, callback contracts, ordering, and duplicate values.
In this chapter8 sections
To sort values, a library function needs to know which value comes first. To search efficiently, it needs data arranged by an agreed rule. C’s qsort and bsearch combine storage information with a callback that supplies that rule.
1. The comparator reports a relationship
A comparator returns a negative value when its first argument comes before its second, zero when they compare equal, and a positive value when it comes after. Only the sign matters. qsort supplies two pointers to elements. bsearch instead supplies the key pointer first and an element pointer second. Our integer example uses the same type for both; a more general key can need a different type.
For ints, (a > b) - (a < b) produces the required sign without overflowing. Returning a - b can overflow for distant signed values. Our example includes INT_MIN and INT_MAX so the comparison is tested at those boundaries.
2. Describe the actual array
#include <assert.h>
#include <limits.h>
#include <stddef.h>
#include <stdlib.h>
static int compare_ints(const void *left, const void *right)
{
int a = *(const int *)left;
int b = *(const int *)right;
return (a > b) - (a < b);
}
int main(void)
{
int values[] = {INT_MAX, -1, 0, INT_MIN, -1};
size_t count = sizeof values / sizeof values[0];
qsort(values, count, sizeof values[0], compare_ints);
assert(values[0] == INT_MIN && values[count - 1] == INT_MAX);
for (size_t i = 1; i < count; ++i) assert(values[i - 1] <= values[i]);
int key = -1;
int *found = bsearch(&key, values, count, sizeof values[0], compare_ints);
assert(found != NULL && *found == -1);
key = 7;
assert(bsearch(&key, values, count, sizeof values[0], compare_ints) == NULL);
assert(bsearch(&key, values, 0, sizeof values[0], compare_ints) == NULL);
qsort(values, 0, sizeof values[0], compare_ints);
return 0;
}
The call supplies the first element, element count, element size, and comparator. The storage must contain the stated elements, and qsort needs to modify them. A pointer cannot reveal its original array count automatically. Compute the count where the complete array is visible, or pass a separately validated count.
3. Equal keys do not promise stable order
A comparison rule must be consistent and define an ordering for the values used. Do not change its answers according to the current element address or an unrelated random choice. If records compare equal by one field, qsort may reorder them. Add a deliberate tie-breaker when your application requires a deterministic order.
The name qsort does not guarantee the quicksort algorithm, a particular complexity bound, or stable sorting. Those are implementation or algorithm-selection questions. Its portable interface promises the ordering behavior under its contract.
4. Search using a compatible arrangement
Our example fully sorts the array before searching with the same comparator. That is a clear sufficient arrangement for bsearch. More precisely, the standard requires a key-relative partition of smaller, equal, and larger elements. The comparator receives the key first and an element second; more complex key types must respect that interface.
A successful result points into the original array. It is not an allocated copy, so do not free it. The array’s lifetime and any later storage changes govern its validity. If several elements compare equal, bsearch may return any matching element; it does not promise the first one.
5. Check absence before using the result
A missing key gives a null pointer. A zero-element search also returns null, but valid pointer arguments are still required. The example passes a real key and real array even for the zero count. Do not use empty-range behavior to justify arbitrary invalid addresses.
If two records have equal keys, must qsort keep their original relative order?
Read the explanation
No. qsort does not promise stable ordering. If a later rule depends on that order, choose a suitable stable algorithm or encode an explicit tie-breaker.
Primary references and further reading
- WG14 N1570 — public C11 draft: 7.22.5: stable C17 searching/sorting contracts.
- WG14 N3096 — public C23 draft: 7.24.5.1: C23 bsearch qualification-sensitive interface.
Before you move on
- A comparator supplies a consistent ordering through the sign of its result.
- qsort may reorder equal elements and does not promise a particular sorting algorithm.
- bsearch needs the required key-relative arrangement and may return any equal match.
Keep these ideas separate
- Comparator subtraction / Safe sign comparison
- Subtracting distant signed keys can overflow; relational comparisons can provide the required sign without that subtraction.
What must stay consistent between sorting an array and searching it with a comparison callback?
Optional: say it aloud or keep a note. You can continue whenever you are ready.Check your understanding
Optional. Answers are not saved or sent, and reading stays unrestricted.
Read the explanation for every choice
- A comparator must always return exactly 1.
A comparison rule must distinguish less, equal, and greater with the required signs.
- All subtraction results are automatically Boolean.
Ordinary integer subtraction is not restricted to zero and one.
- Signed subtraction can overflow and fail to express a valid ordering.
✓ Correct reasoning. Use safe comparisons and a consistent ordering contract instead of relying on a potentially overflowing difference.
C17
Ready for the next idea?
Mark this chapter as read whenever you feel ready.