C, lesson 12
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.
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:
2 exercises to try what you just read.
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).
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.
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 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.
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 25struct 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 30Input:
3
502 199
117 1250
330 5
330
999
117
Output:
330: 0.05
999: not found
117: 12.50