Week 78 of 125
TAOCP 5.2.2 Sorting by Exchanging
Sign up or sign in to tick these off and give this week a due date.
-
Bubble sort and its analysis, Batcher's parallel merge exchange, quicksort with careful analysis of its average case, and radix exchange sort, which partitions on bits.
Time About 10 hours this week
Why it matters
Quicksort is the most used sorting algorithm in the world. Knuth's analysis shows exactly why choosing the pivot and handling small subarrays matter.
Before you start
- 5.2.1 Sorting by Insertion
- 1.2.7 Harmonic Numbers
How to approach it
Implement quicksort carefully with Knuth's partitioning scheme, a cutoff to insertion sort, and median-of-three. Test on sorted input, reverse-sorted input and all-equal keys. Read the bubble sort analysis for technique; bubble sort itself is not worth using.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Quadratic behavior on sorted input with a naive pivot.
- Partitioning bugs with equal keys, the most common real-world quicksort failure.
- Unbounded recursion depth: recurse on the smaller side first.