C08-Sorting-in-Linear-Time/8.3.md
Using Figure 8.3 as a model, illustrate the operation of 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.
Answer| 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 | ROG |
| BIG | ROW | NOW | SEA |
| TEA | NOW | BOX | TAB |
| NOW | BOX | FOX | TAR |
| FOX | FOX | ROG | TEA |
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?
Answer给每个item都增加一个原始index属性，最后相同的元素根据index再排一次.需要O(n)的额外空间.
Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?
Answer循环不变式:每次for循环前，最后的i-1个数字是排好序的.
Initialization:循环还没开始，0个数字，是排好的.
Maintenance:排第i个数字时，如果数字不相同，那肯定是排号序的，如果相同，因为采用stable的COUNTTING-SORT算法，后面的i-1位是排好序的，所以能保持性质.
Termination:最后是排好序的.
Show how to sort n integers in the range 0 to n^2 - 1 in O(n) time.
Note: In 3rd Edition, the number range is 0 to n^3 - 1, the basic idea is same
Answer将这些数字看成n进制，使用radix-sort.
The running time is O(4n) = O(n)
The radix sort running time is O(d * (n + k)) , where d is the number of digit, n is the number of elements, and k is the number of possible values.
In this case, k equals n. So the total running time is O(2 * (n + n)) = O(4n) = O(n)
Naive Implementation with a lot of copy: implementation
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?
Answer从最高位往后面排序不是一种好办法，需要递归去做. 需要k^d次. 要同时care nk堆数据.
Follow @louis1992 on github to help finish this task.