8.3 Radix sort
8.3-1
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| 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
Insertion sort and merge sort are stable, heapsort and quicksort are not stable.
We can create an additional array to record the index of each element in the original array. When comparing two elements, if they are not equal, we compare them in the usualy way, if they are equal, we compare their indices.
The scheme doesn't affect the running time since the new comparision method still requires O(1), but it needs additional O(n) space.
8.3-3
We use the following loop invariant:
At the start of each iteration of the for loop of 1-2 lines, the n-digit numbers are sorted by digit 1 to i - 1.
Initialization: Prior to the first iteration of the loop, i = 1, digit 1 to i - 1 contains 0 digit, thus we can say the n-digit numbers are sorted by digit 1 to 0.
Maintenance: After the ith iteration, the numbers are sorted in the ith digit, because we used a stable sorting algorithm, so if two numbers has same value on digit i, it won't change their relative order, and digit 1 to digit i - 1 is already sorted, so digit 1 to digit i is sorted.
Termination: At termination, i = d + 1, numbers are sorted by digit 1 to digit d, so the array is sorted.
We need the assumption in the maintenance step.
8.3-4
We can treat the numbers are in base n, each number contains 3 digits, thus the max number is $(n - 1)n^2 + (n - 1)n + (n - 1) = n^3 - 1$, so d = 3. There are n possible values in each digit, so k = n, so we can use the radix sort to sort the numbers. The running time is $d\Theta(n + k) = 3\Theta(n + n) = \Theta(n)$, which is also O(n).