8.3 Radix sort

8.3-1

Using Figure 8.3 as a model, illustrate the operation of $\text{RADIX-SORT}$ on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.

$$ \begin{array}{cccc} 0 & 1 & 2 & 3 \\ \hline \text{COW} & \text{SE$\textbf{A}$} & \text{T$\textbf{A}$B} & \text{$\textbf{B}$AR} \\ \text{DOG} & \text{TE$\textbf{A}$} & \text{B$\textbf{A}$R} & \text{$\textbf{B}$IG} \\ \text{SEA} & \text{MO$\textbf{B}$} & \text{E$\textbf{A}$R} & \text{$\textbf{B}$OX} \\ \text{RUG} & \text{TA$\textbf{B}$} & \text{T$\textbf{A}$R} & \text{$\textbf{C}$OW} \\ \text{ROW} & \text{DO$\textbf{G}$} & \text{S$\textbf{E}$A} & \text{$\textbf{D}$IG} \\ \text{MOB} & \text{RU$\textbf{G}$} & \text{T$\textbf{E}$A} & \text{$\textbf{D}$OG} \\ \text{BOX} & \text{DI$\textbf{G}$} & \text{D$\textbf{I}$G} & \text{$\textbf{E}$AR} \\ \text{TAB} & \text{BI$\textbf{G}$} & \text{B$\textbf{I}$G} & \text{$\textbf{F}$OX} \\ \text{BAR} & \text{BA$\textbf{R}$} & \text{M$\textbf{O}$B} & \text{$\textbf{M}$OB} \\ \text{EAR} & \text{EA$\textbf{R}$} & \text{D$\textbf{O}$G} & \text{$\textbf{N}$OW} \\ \text{TAR} & \text{TA$\textbf{R}$} & \text{C$\textbf{O}$W} & \text{$\textbf{R}$OW} \\ \text{DIG} & \text{CO$\textbf{W}$} & \text{R$\textbf{O}$W} & \text{$\textbf{R}$UG} \\ \text{BIG} & \text{RO$\textbf{W}$} & \text{N$\textbf{O}$W} & \text{$\textbf{S}$EA} \\ \text{TEA} & \text{NO$\textbf{W}$} & \text{B$\textbf{O}$X} & \text{$\textbf{T}$AB} \\ \text{NOW} & \text{BO$\textbf{X}$} & \text{F$\textbf{O}$X} & \text{$\textbf{T}$AR} \\ \text{FOX} & \text{FO$\textbf{X}$} & \text{R$\textbf{U}$G} & \text{$\textbf{T}$EA} \\ \end{array} $$

8.3-2

Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?

Insertion sort and merge sort are stable. Heapsort and quicksort are not.

To make any sorting algorithm stable we can preprocess, replacing each element of an array with an ordered pair. The first entry will be the value of the element, and the second value will be the index of the element.

For example, the array $[2, 1, 1, 3, 4, 4, 4]$ would become $[(2, 1), (1, 2), (1, 3), (3, 4), (4, 5), (4, 6), (4, 7)]$. We now interpret $(i, j) < (k, m)$ if $i < k$ or $i = k$ and $j < m$. Under this definition of less-than, the algorithm is guaranteed to be stable because each of our new elements is distinct and the index comparison ensures that if a repeat element appeared later in the original array, it must appear later in the sorted array. This doubles the space requirement, but the running time will be asymptotically unchanged.

8.3-3

Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?

Loop invariant: At the beginning of the for loop, the array is sorted on the last $i − 1$ digits.

Initialization: The array is trivially sorted on the last $0$ digits.

Maintenance: Let's assume that the array is sorted on the last $i − 1$ digits. After we sort on the $i$th digit, the array will be sorted on the last $i$ digits. It is obvious that elements with different digit in the $i$th position are ordered accordingly; in the case of the same $i$th digit, we still get a correct order, because we're using a stable sort and the elements were already sorted on the last $i − 1$ digits.

Termination: The loop terminates when $i = d + 1$. Since the invariant holds, we have the numbers sorted on $d$ digits.

8.3-4

Show how to sort $n$ integers in the range $0$ to $n^3 - 1$ in $O(n)$ time.

First run through the list of integers and convert each one to base $n$, then radix sort them. Each number will have at most $\log_n n^3 = 3$ digits so there will only need to be $3$ passes. For each pass, there are $n$ possible values which can be taken on, so we can use counting sort to sort each digit in $O(n)$ time.

8.3-5 $\star$

In the first card-sorting algorithm in this section, exactly how many sorting passes are needed to sort $d$-digit decimal numbers in the worst case? How many piles of cards would an operator need to keep track of in the worst case?

Given $n$ $d$-digit numbers in which each digit can take on up to $k$ possible values, we'll perform $\Theta(k^d)$ passes and keep track of $\Theta(nk)$ piles in the worst case.