TAOCP 5.2.5: Sorting by Distribution
Section 5.2.5 exercises: 18/18 solved.
Section 5.2.5. Sorting by Distribution
Exercises from TAOCP Volume 3 Section 5.2.5: 18/18 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | ▶ [20] | medium | solved | 1m19s |
| 2 | [13] | simple | verified | 1m25s |
| 3 | [15] | simple | 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 |
| 10 | [30] | hard | solved | 13m58s |
| 11 | [16] | medium | solved | 4m52s |
| 12 | [24] | medium | solved | 3m57s |
| 13 | [40] | project | solved | 8m40s |
| 14 | [22] | medium | solved | 51m29s |
| 15 | [22] | medium | solved | 46m52s |
| 16 | ▶ [25] | medium | solved | 22m31s |
| 17 | [15] | simple | solved | 1m41s |
| 18 | [HM26] | hm-hard | solved | 7m35s |
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$.
TAOCP 5.2.5 Exercise 10
We consider the same record structure as in Algorithm R (Section 5.
TAOCP 5.2.5 Exercise 11
The input file consists of the 16 three‑digit numbers (with leading zeros) \[ \begin{array}{c|c} \text{index} & \text{value} \\ \hline 1 & 503 \\
TAOCP 5.2.5 Exercise 12
After Algorithm R has processed the \(p\) leading digits, the records \(R_1,\dots,R_N\) are linked together in a list that starts at pointer \(P\).
TAOCP 5.2.5 Exercise 13
We consider the problem of sorting \(N\) records with keys that are two-digit numbers in base \(M = \lceil \sqrt{N} \rceil\).
TAOCP 5.2.5 Exercise 14
We need to solve exercise 14 from TAOCP Vol 3, section 5.
TAOCP 5.2.5 Exercise 15
We need to solve Exercise 15 from TAOCP Volume 3, Section 5.
TAOCP 5.2.5 Exercise 16
**Algorithm S (Radix list sort for variable‑length strings).