TAOCP 5.2 Exercise 6
We simulate Algorithm D (Distribution counting) on the 16 records: | \(j\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |------|---|---|---|---|---|---|---|---|---|----|---...
Exercise 6. [18] Simulate Algorithm D by hand, showing intermediate results when the 16 records 5T, 0C, 5U, 0O, 9., 1B, 8S, 2R, 6A, 4A, 1G, 5L, 6T, 6I, 7O, 7N are being sorted. Here the numeric digit is the key, and the alphabetic information is just carried along with the records.
Verified: yes
Solve time: 8m10s
Solution
We simulate Algorithm D (Distribution counting) on the 16 records:
| (j) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| (R_j) | 5T | 0C | 5U | 0O | 9. | 1B | 8S | 2R | 6A | 4A | 1G | 5L | 6T | 6I | 7O | 7N |
| (K_j) | 5 | 0 | 5 | 0 | 9 | 1 | 8 | 2 | 6 | 4 | 1 | 5 | 6 | 6 | 7 | 7 |
The keys are integers in the range (u = 0) to (v = 9).
Step D1: Clear COUNTs
[ \text{COUNT}[0\ldots 9] = 0. ]
Steps D2-D3: Count occurrences
For (j = 1) to (16), increment (\text{COUNT}[K_j]).
| Key | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| (\text{COUNT}) after D3 | 2 | 2 | 1 | 0 | 1 | 3 | 3 | 2 | 1 | 1 |
Step D4: Accumulate
For (i = 1) to (9): (\text{COUNT}[i] \leftarrow \text{COUNT}[i] + \text{COUNT}[i-1]).
| (i) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| (\text{COUNT}[i]) | 4 | 5 | 5 | 6 | 9 | 12 | 14 | 15 | 16 |
Full array after D4: [ \text{COUNT} = [2,;4,;5,;5,;6,;9,;12,;14,;15,;16] \quad (\text{indices } 0\ldots 9). ]
Steps D5-D6: Distribute records to output (S[1\ldots 16])
For (j = 16) down to (1): [ i \leftarrow \text{COUNT}[K_j], \quad S_i \leftarrow R_j, \quad \text{COUNT}[K_j] \leftarrow i-1. ]
| (j) | (R_j) | (K_j) | (\text{COUNT}[K_j]) before | (i) | (S_i = R_j) | (\text{COUNT}[K_j]) after |
|---|---|---|---|---|---|---|
| 16 | 7N | 7 | 14 | 14 | (S_{14}=7N) | 13 |
| 15 | 7O | 7 | 13 | 13 | (S_{13}=7O) | 12 |
| 14 | 6I | 6 | 12 | 12 | (S_{12}=6I) | 11 |
| 13 | 6T | 6 | 11 | 11 | (S_{11}=6T) | 10 |
| 12 | 5L | 5 | 9 | 9 | (S_9=5L) | 8 |
| 11 | 1G | 1 | 4 | 4 | (S_4=1G) | 3 |
| 10 | 4A | 4 | 6 | 6 | (S_6=4A) | 5 |
| 9 | 6A | 6 | 10 | 10 | (S_{10}=6A) | 9 |
| 8 | 2R | 2 | 5 | 5 | (S_5=2R) | 4 |
| 7 | 8S | 8 | 15 | 15 | (S_{15}=8S) | 14 |
| 6 | 1B | 1 | 3 | 3 | (S_3=1B) | 2 |
| 5 | 9. | 9 | 16 | 16 | (S_{16}=9.) | 15 |
| 4 | 0O | 0 | 2 | 2 | (S_2=0O) | 1 |
| 3 | 5U | 5 | 8 | 8 | (S_8=5U) | 7 |
| 2 | 0C | 0 | 1 | 1 | (S_1=0C) | 0 |
| 1 | 5T | 5 | 7 | 7 | (S_7=5T) | 6 |
Final sorted output
[ \begin{array}{c|c} i & S_i \ \hline 1 & 0C \ 2 & 0O \ 3 & 1B \ 4 & 1G \ 5 & 2R \ 6 & 4A \ 7 & 5T \ 8 & 5U \ 9 & 5L \ 10 & 6A \ 11 & 6T \ 12 & 6I \ 13 & 7O \ 14 & 7N \ 15 & 8S \ 16 & 9. \ \end{array} ]
The keys appear in non‑decreasing order: (0,0,1,1,2,4,5,5,5,6,6,6,7,7,8,9). The algorithm is stable: records with equal keys retain their original relative order.
\boxed{0C,\ 0O,\ 1B,\ 1G,\ 2R,\ 4A,\ 5T,\ 5U,\ 5L,\ 6A,\ 6T,\ 6I,\ 7O,\ 7N,\ 8S,\ 9.}