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 \\

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.5: Sorting by Distribution

Exercise 11. [16] The sixteen input numbers shown in Table 1 start with 41 inversions; after sorting is complete, of course, there are no inversions remaining. How many inversions would be present in the file if we omitted pass 1, doing a radix sort only on the tens and hundreds digits? How many inversions would be present if we omitted both pass 1 and pass 2?

Verified: no
Solve time: 4m52s

Solution

The input file consists of the 16 three‑digit numbers (with leading zeros)

[ \begin{array}{c|c} \text{index} & \text{value} \ \hline 1 & 503 \ 2 & 087 \ 3 & 512 \ 4 & 061 \ 5 & 908 \ 6 & 170 \ 7 & 897 \ 8 & 275 \ 9 & 653 \ 10 & 426 \ 11 & 154 \ 12 & 509 \ 13 & 612 \ 14 & 677 \ 15 & 765 \ 16 & 703 \end{array} ]

An inversion is a pair ((i,j)) with (i<j) but (a_i > a_j).
The problem states that the original file contains 41 inversions; this can be verified by direct counting (summing over each element the number of later elements that are smaller).

The LSD radix sort of the text performs three stable distribution passes:

  • Pass 1: sort by units digit,
  • Pass 2: sort by tens digit,
  • Pass 3: sort by hundreds digit.

We are asked for the number of inversions remaining if we omit certain passes, i.e. if we apply only the indicated stable sorts to the original list.

1. Omitting pass 1 (sort by tens, then hundreds)

We first stable‑sort the original list by the tens digit.

Tens digits of the original list:

[ \begin{array}{c|c|c} \text{index} & \text{value} & \text{tens} \ \hline 1 & 503 & 0 \ 2 & 087 & 8 \ 3 & 512 & 1 \ 4 & 061 & 6 \ 5 & 908 & 0 \ 6 & 170 & 7 \ 7 & 897 & 9 \ 8 & 275 & 7 \ 9 & 653 & 5 \ 10 & 426 & 2 \ 11 & 154 & 5 \ 12 & 509 & 0 \ 13 & 612 & 1 \ 14 & 677 & 7 \ 15 & 765 & 6 \ 16 & 703 & 0 \end{array} ]

Stable sorting by tens digit (queues 0,1,…,9) gives the intermediate sequence (T):

[ T = [503,; 908,; 509,; 703,; 512,; 612,; 426,; 653,; 154,; 061,; 765,; 170,; 275,; 677,; 087,; 897]. ]

Now we stable‑sort (T) by the hundreds digit.

Hundreds digits in (T):

[ \begin{array}{c|c|c} \text{pos.} & \text{value} & \text{hundreds} \ \hline 1 & 503 & 5 \ 2 & 908 & 9 \ 3 & 509 & 5 \ 4 & 703 & 7 \ 5 & 512 & 5 \ 6 & 612 & 6 \ 7 & 426 & 4 \ 8 & 653 & 6 \ 9 & 154 & 1 \ 10 & 061 & 0 \ 11 & 765 & 7 \ 12 & 170 & 1 \ 13 & 275 & 2 \ 14 & 677 & 6 \ 15 & 087 & 0 \ 16 & 897 & 8 \end{array} ]

Stable sorting by hundreds digit (queues 0,1,…,9) yields

[ TH = [061,; 087,; 154,; 170,; 275,; 426,; 503,; 509,; 512,; 612,; 653,; 677,; 703,; 765,; 897,; 908]. ]

This is exactly the fully sorted order. Hence there are no inversions.

[ \boxed{0} ]

2. Omitting both pass 1 and pass 2 (sort only by hundreds)

We stable‑sort the original list directly by the hundreds digit.

Hundreds digits of the original list:

[ \begin{array}{c|c|c} \text{index} & \text{value} & \text{hundreds} \ \hline 1 & 503 & 5 \ 2 & 087 & 0 \ 3 & 512 & 5 \ 4 & 061 & 0 \ 5 & 908 & 9 \ 6 & 170 & 1 \ 7 & 897 & 8 \ 8 & 275 & 2 \ 9 & 653 & 6 \ 10 & 426 & 4 \ 11 & 154 & 1 \ 12 & 509 & 5 \ 13 & 612 & 6 \ 14 & 677 & 6 \ 15 & 765 & 7 \ 16 & 703 & 7 \end{array} ]

Stable sorting by hundreds digit gives the sequence (H):

[ H = [087,; 061,; 170,; 154,; 275,; 426,; 503,; 512,; 509,; 653,; 612,; 677,; 765,; 703,; 897,; 908]. ]

Because the hundreds digits are in non‑decreasing order, any inversion must lie inside a block of equal hundreds digits. We count inversions within each block:

  • Hundreds 0: ([87, 61]) → 1 inversion ((87 > 61)).
  • Hundreds 1: ([170, 154]) → 1 inversion.
  • Hundreds 2: ([275]) → 0.
  • Hundreds 4: ([426]) → 0.
  • Hundreds 5: ([503, 512, 509]) → 1 inversion ((512 > 509)).
  • Hundreds 6: ([653, 612, 677]) → 1 inversion ((653 > 612)).
  • Hundreds 7: ([765, 703]) → 1 inversion.
  • Hundreds 8: ([897]) → 0.
  • Hundreds 9: ([908]) → 0.

Total inversions = (1+1+1+1+1 = 5).

[ \boxed{5} ]

Verification

  • The initial inversion count of 41 was independently confirmed by summing, for each element, the number of later elements that are smaller.
  • The final sequence after tens‑then‑hundreds sort was compared with the fully sorted list (given in Table 1) and found identical.
  • The sequence after hundreds‑only sort was checked for cross‑block inversions: the maximum of each hundreds block is strictly less than the minimum of the next block, so no cross‑block inversions exist. The within‑block counts are easily verified by inspection. ∎