Chapter 8.3
ch8.3
8.3-1
--- --* -*- *-- COW SEA TAB BAR DOG TEA BAR BIG SEA MOB EAR BOX RUG TAB TAR COW ROW DOG SEA DIG MOB RUG TEA DOG BOX DIG DIG EAR TAB -> BIG -> BIG -> FOX BAR BAR MOB MOB EAR EAR DOG NOW TAR TAR COW ROW DIG COW ROW RUG BIG ROW NOW SEA TEA NOW BOX TAB NOW BOX FOX TAR FOX FOX RUG TEA
8.3-2
The insertion sort and merge sort algorithms are stable, the heapsort and quicksort algorithms are not stable.
We could store and compare the original indices of the identical elements to make any comparison sorting algorithm stable. The additional time does not asymptotically affect the running time, the additional space is \(n\lg n\) bits if we use \(\lg n\) bits to store the index of an element.
8.3-3
Loop invariant: At the start of each iteration, the array is \(1..i-1\) digits radix sorted.
Initialization: The 0 digits are radix sorted.
Maintenance: In the \(i\)th iteration, we use a stable sort to sort the array on digit \(i\), for two elements a and b, notate the \(ith\) digit with \(a_i\) and \(b_i\), if \(a_i > b_i\) then \(a > b\), if \(a_i < b_i\) then \(a < b\), if \(a_i = b_i\) then the order of \(a\) and \(b\) remains as they were \(1..i-1\) digits radix sorted. Thus the array is \(1..i\) digits radix sorted after the stable sort.
Termination: When the loop terminates, the array is \(1..d\) digits radix sorted.
We need the assumption that the intermediate sort is stable, when the \(ith\) digits of two elements are the same.
8.3-4
From Lemma 8.4, we have
\begin{align*} T(n)&=\Theta((b/r)(n+2^r)) &, b=3\lg n \end{align*}Because \(b=3\lg n \geq \lfloor \lg n \rfloor\), we choose \(r=\lfloor\lg n \rfloor\) to yield a running time of \(\Theta(bn/\lg n) = \Theta(n)\).
In despite of the low level bits, we could simply perform a \(3\)-digit radix sort on the integers, each digit holds \(0\) to \(n - 1\).
8.3-5
In the worst case, we need \(d\) sorting passes to sort \(d\)-digit decimal numbers, and an operator need to keep track of \(10\) piles of cards.