Week 77 of 125
TAOCP 5.2.1 Sorting by Insertion
Sign up or sign in to tick these off and give this week a due date.
-
Straight insertion, binary insertion, Shellsort with diminishing increments, list insertion, and address-calculation sorting, each with careful analysis.
Time About 9 hours this week
Why it matters
Insertion sort is what fast library sorts use for small subarrays. Shellsort is still a practical choice in embedded code with no recursion.
Before you start
- 5.1.1 Inversions
- 1.2.10 Analysis of an Algorithm
How to approach it
Implement straight insertion and Shellsort with a few increment sequences. Count comparisons and moves on random data and compare with Knuth's formulas and tables.
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
- Shellsort performance depends hugely on the increment sequence. Do not use powers of two.
- Using binary insertion and expecting big wins on arrays: moves still cost O(n^2).