TAOCP 5.2.5: Sorting by Distribution
Section 5.2.5 exercises: 9/9 solved.
Section 5.2.5. Sorting by Distribution
Exercises from TAOCP Volume 3 Section 5.2.5: 9/9 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | solved | 1m19s | |
| 2 | [**] | verified | 1m25s | |
| 3 | [**] | verified | 1m30s | |
| 4 | [23] | medium | verified | 4m43s |
| 5 | [20] | medium | solved | 3m46s |
| 6 | [M24] | math-medium | solved | 4m13s |
| 7 | [20] | medium | verified | 1m16s |
| 8 | [20] | medium | verified | 1m50s |
| 9 | [20] | medium | verified | 1m51s |
TAOCP 5.2.5 Exercise 1
The distribution sort of Exercise 5.
TAOCP 5.2.5 Exercise 2
Algorithm R performs a sequence of $p$ distribution passes, each pass grouping records into $M$ FIFO queues according to a single digit $a_{p+1-k}$.
TAOCP 5.2.5 Exercise 3
At the start, Algorithm H sets $i \leftarrow 0$ and then sets $P \leftarrow \mathrm{TOP}[0]$.
TAOCP 5.2.5 Exercise 4
The reviewer’s objection is correct: simply replacing FIFO queues by LIFO stacks breaks stability.
TAOCP 5.2.5 Exercise 5
The previous solution’s structural idea is essentially correct, but the running-time analysis must be rebuilt using Knuth’s original definition of the cost components of Program R, in which the parame...
TAOCP 5.2.5 Exercise 6
The key issue in the previous argument is not the final probabilistic model, but the unjustified claim that pile-wise conditional contributions remain independent in a way that produces a product of t...
TAOCP 5.2.5 Exercise 7
Algorithm R and radix exchange sorting both exploit the representation of keys as digit sequences and avoid direct key-to-key comparison.
TAOCP 5.2.5 Exercise 8
Let the radix be $M$ and let keys be written as $(a_1,a_2,\dots,a_p)$ with digits $0 \le a_i < M$.
TAOCP 5.2.5 Exercise 9
Let a signed magnitude key be a $p$-tuple $(s, a_2, a_3, \dots, a_p),$ where $s \in {0,1}$ is the sign digit and $(a_2,\dots,a_p)$ is the magnitude expressed in radix $M$.