Drills
Five tasks.
1. Compute k for a Title key
Step 6's table left the last row blank.
Say a title is up to 20 characters from a 32-letter alphabet. How many possible
values? How many bytes would a count array of int32 occupy?
Compare with the mass of the Earth in grams (≈6×10²⁷). Write both numbers down.
2. CountingSortByYear
Counting sort on Year in a single pass, k = 131.
Compare with RadixSortByYear — four passes at k = 10. Which is faster for this
range? At what range width would radix start winning?
3. When k is larger than n
Generate 100 items. Sort them by Year with counting sort.
How many slots does the count array have? How many items? Which part of
O(n + k) dominates?
Then raise MaxYear to 1,000,000 and repeat. At what point does it become
absurd?
4. Negative and non-integer keys
Rating is 0–100. What if it were −50…+50? What if it were a float64 from 0
to 5?
Adapt CountingSortByRating for the first case. For the second, explain why it
cannot be done directly, and propose what you would have to do to the key.
5. Break radix sort a different way
Step 7 broke the inner pass. Now break the order: sort the digits from the most significant to the least (MSD instead of LSD), keeping the inner pass stable.
Is the result correct? Why does LSD work when this does not — and what would an MSD radix sort have to do differently to work?