Skip to content

Latest commit

 

History

History
75 lines (54 loc) · 2.89 KB

8.3.md

File metadata and controls

75 lines (54 loc) · 2.89 KB
Raw

Exercises 8.3-1

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

Exercises 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?

Answer

  • stable: insertion sort, merge sort
  • not stable: heapsort, quicksort

给每个item都增加一个原始index属性，最后相同的元素根据index再排一次.需要O(n)的额外空间.

Exercises 8.3-3

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:最后是排好序的.

Exercises 8.3-4

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

Exercises 8.3-5

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.