Card 10/ 11
Practice: Choosing a Sort for Three Sensor Logs
Temperatures in whole degrees, 64-bit device ids and readings spread evenly between 0 and 1: pick a sort for each.
Choosing a linear-time sort means reading the keys before reading any code: their type, their range, and how they are spread decide which sort applies, or whether none does. This exercise practises that decision on three logs from the same fleet of weather stations.
Each log holds a million entries, and each has to be sorted by one field.
- Temperatures, in whole degrees Celsius. The stations' sensors report from −40 to 60 and nothing outside it.
- Device ids, unsigned 64-bit integers assigned at random over their whole range, one per entry.
- Readings from a calibration sensor, floating-point fractions from 0 up to but not including 1, which the manufacturer states are spread evenly.
For each log, choose counting sort, radix sort, bucket sort or a comparison sort, and give the property of the keys that decides it. Then estimate the work in counters, passes or buckets.
Show a choice for each log
| Log | n | Range or spread | Sort | Why |
|---|---|---|---|---|
| Temperatures | 1,000,000 | −40 to 60, so k = 101 | Counting sort | n + k = 1,000,101 steps and 101 counters |
| Device ids | 1,000,000 | 0 to 2⁶⁴ − 1 | Radix sort, 16 bits per digit | Counting sort would need 2⁶⁴ counters; 4 passes cost about 4 × (n + 65,536) = 4,262,144 steps |
| Readings | 1,000,000 | 0 to 1, spread evenly | Bucket sort with n buckets | Not integers, so counting and radix sort do not apply directly; evenly spread keys put O(1) items in each bucket |
The temperatures are integers in a range of 101 values against a million items, so k is tiny next to n and counting sort's O(n + k) is O(n). Subtract −40, the smallest key, so the count array starts at it.
The device ids are integers too, but their range is the whole of 64 bits, and counting sort's array of 2⁶⁴ counters, about 1.8 × 10¹⁹, could not be allocated on any machine. Radix sort cuts each id into four 16-bit digits and runs four counting passes of 65,536 counters. Eight passes of 8-bit digits work as well, at about 8,002,048 steps, trading fewer counters for more passes. Either is well below the roughly 19,931,569 comparisons n log₂ n predicts for a comparison sort, though a pass step and a comparison do not cost the same.
The readings are not integers, which rules out indexing by the key itself, but they are spread evenly over a known range, which is the one assumption bucket sort needs. With a million buckets, a reading's bucket is the reading times a million, rounded down. Had the manufacturer not promised an even spread, a comparison sort would be the safe choice, because a cluster of readings would put most of them in a few buckets.
A run sorted a sample of 10,000 entries per log this way, with counting sort for the temperatures, four 16-bit radix passes for the ids and bucket sort for the readings, and each output matched Python's sorted.
← → move through sections and cards