Skip to content

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 is stable. When inserting $A[j]$ into the sorted sequence $A[1..j - 1]$, we do it the following way: compare $A[j]$ to $A[i]$, starting with $i = j - 1$ and going down to $i = 1$. Continue at long as $A[j] < A[i]$.

  • Merge sort as defined is stable, because when two elements compared are equal, the tie is broken by taking the element from array $L$ which keeps them in the original order.

  • Heapsort and quicksort are not stable.

One scheme that makes a sorting algorithm stable is to store the index of each element (the element's place in the original ordering) with the element. When comparing two elements, compare them by their values and break ties by their indices.

Additional space requirements: For $n$ elements, their indices are $1 \ldots n$. Each can be written in $\lg n$ bits, so together they take $O(n\lg n)$ additional space.

Additional time requirements: The worst case is when all elements are equal. The asymptotic time does not change because we add a constant amount of work to each comparison.

8.3-3

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

Basis: If $d = 1$, there's only one digit, so sorting on that digit sorts the array.

Inductive step: Assuming that radix sort works for $d - 1$ digits, we'll show that it works for $d$ digits.

Radix sort sorts separately on each digit, starting from digit $1$. Thus, radix sort of $d$ digits, which sorts on digits $1, \ldots, d$ is equivalent to radix sort of the low-order $d - 1$ digits followed by a sort on digit $d$. By our induction hypothesis, the sort of the low-order $d - 1$ digits works, so just before the sort on digit $d$, the elements are in order according to their low-order $d - 1$ digits.

The sort on digit $d$ will order the elements by their $d$th digit. Consider two elements, $a$ and $b$, with dth digits $a_d$ and $b_d$ respectively.

  • If $a_d < b_d$, the sort will put $a$ before $b$, which is correct, since $a < b$ regardless of the low-order digits.
  • If $a_d > b_d$, the sort will put $a$ after $b$, which is correct, since $a > b$ regardless of the low-order digits.
  • If $a_d = b_d$, the sort will leave $a$ and $b$ in the same order they were in, because it is stable. But that order is already correct, since the correct order of $a$ and $b$ is determined by the low-order $d - 1$ digits when their dth digits are equal, and the elements are already sorted by their low-order $d - 1$ digits.

If the intermediate sort were not stable, it might rearrange elements whose $d$th digits were equal—elements that were in the right order after the sort on their lower-order digits.

8.3-4

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

Treat the numbers as $3$-digit numbers in radix $n$. Each digit ranges from $0$ to $n - 1$. Sort these $3$-digit numbers with radix sort.

There are $3$ calls to counting sort, each taking $\Theta(n + n) = \Theta(n)$ time, so that the total time is $\Theta(n)$.

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?

  • Since a pass consists of one iteration of the loop on line 1–2, only $d$ passes are needed.
  • Since each of the digits can be one of ten decimal numbers, the most number of piles that would be needed to be kept track of is $10$.