算法分析与设计31授课教案07sorting in linear time

1、Design and Analysis of AlgorithmsSorting in linear timeReference: CLRS Chapter 8Topics: Lower bound for sorting Counting sort Radix sort Bucket sortHuo Hongwei1How fast can we sort?All the sorting algorithms we have seen so far are comparison sorts: only use comparisons to determine the relative ord

2、er of elements. E.g., insertion sort, merge sort, quicksort, heapsort. The best worst-case running time that weve seen for comparison sorting is O(n lg n).Q: Is O(n lg n) the best we can do?A: Yes, as long as we use comparison sortsTODAY: Prove any comparison sort has W(n lg n) worst case running ti

3、meHuo Hongwei2Decision-tree example1:2Sort <a1, a2, , an>2:31:31:32:3for i, j Î 1, 2, n.Each internal node is labelled i:j The left subtree shows subsequent comparisons if ai £aj. The right subtree shows subsequent comparisons if ai³ aj.Huo Hongwei3321231312132213123Decision-tre

4、e example1:29 ³ 41:3Sort <a1, a2, a3> = <9, 4, 6>2:31:32:3Each internal node is labelled i:j for i, j Î 1, 2, n. The left subtree shows subsequent comparisons if ai £aj. The right subtree shows subsequent comparisons if ai³ aj.Huo Hongwei4321231312132213123Decision-tr

5、ee example1:2Sort <a1, a2, a3> = <9, 4, 6>2:31:39 ³ 61:32:3Each internal node is labelled i:j for i, j Î 1, 2, n. The left subtree shows subsequent comparisons if ai £aj. The right subtree shows subsequent comparisons if ai³ aj.Huo Hongwei5321231312132213123Decision-t

6、ree example1:2Sort <a1, a2, a3> = <9, 4, 6>2:31:31:32:34 £ 6Each internal node is labelled i:j for i, j Î 1, 2, n. The left subtree shows subsequent comparisons if ai £aj. The right subtree shows subsequent comparisons if ai³ aj.Huo Hongwei6321231312132213123Decision-

7、tree example1:2Sort <a1, a2, a3> = <9, 4, 6>2:31:31:32:34 £ 6 £ 9Each leaf contains a permutation <p(1), p(2), , p(n)> to indicate that the ordering ap(1) £ ap(2) £ £ ap(n) has been established.Huo Hongwei7321231312132213123Decision-tree mA decision tree ca

8、n m comparison sort:the execution of any One tree for each input size n. View the algorithm as splitting whenever it compares two elements. The tree contains the comparisons along all possible instruction traces. The running time of the algorithm = the length of the path taken. Worst-case running ti

9、me = height of tree.Huo Hongwei8Any comparison sortCan be turned into a Decision tree2:3Huo Hongwei9321231312132INSERTION SORTINSERTION-SORT(A)1:21 for j ¬ 2 to length(A)2 do key ¬ Aj3 / insert Aj into the so 2:3 quence A1.j-11:34i ¬ j 15 while i > 0 and Ai > key6 do Ai+1 ¬

10、/ move 1:3 back7 i ¬ i 8 Ai+1 ¬ key /find the insertion position2131231Lower Bound for decision-tree SortingTheorem. Any comparison sorting algorithm requires W(nlg n) comparisons in the worst case.Proof. Worst case dictated by tree height h. n! different orderings. One (or more) leaves co

11、rresponding to each ordering. Binary tree with n! leaves must have heighth ³ lg (n!)³ lg (n /e)n= n lgn n lg e= W(n lg n)lg is mono. increasingStirling's formulaHuo Hongwei10Lower Bound for Comparision SortingCorollary.Heapsort and merge sort are asymptoticallyoptimal comparison sortin

12、g algorithms.Huo Hongwei11Sorting Lower boundIs there a faster algorithm?If different mof computation?Huo Hongwei12INSERTION SORTINSERTION-SORT(A)1 for j ¬ 2 to length(A)2 do key ¬ Aj3 / insert Aj into the sorted sequence A1.j-14i ¬ j 15 while i > 0 and Ai > key6 do Ai+1 ¬

13、Ai / move item back7i ¬ i 18Ai+1 ¬ key /find the insertion positionSorting in linear timeCounting sort: No comparisons between elements. Input: A1 . . n, where A jÎ1, 2, , k. Output: B1 . . n, sorted. Auxiliary storage: C1 . . k.Huo Hongwei13Counting SortHuo Hongwei14COUNTING SORTCOUN

14、TING-SORT(A, B, k)1 for i ¬ 1 to k2 do Ci ¬ 03 for j ¬ 1 to lengthA4do CAj ¬ CAj+15 /Ci now contains the number of elements equal to i.6 for i ¬ 2 to k7do Ci ¬ Ci+ Ci-18 /Ci now contains the number of elements less than or equal to i.9 for j ¬ lengthA downto 110do

15、BCAj ¬ Aj 11CAj ¬ CAj-1Counting-sort example123451234A:C:B:Huo Hongwei1541343Counting-sort exampleLoop1123451234A:C:B:for i ¬ 1 to kdo Ci ¬ 0Huo Hongwei16000041343Counting-sort exampleLoop2123451234A:C:B:for j ¬ 1 to ndo CA j ¬ CA j + 1/ Ci = |key = i|Huo Hongwei1700014

16、1343Counting-sort exampleLoop2123451234A:C:B:for j ¬ 1 to ndo CA j ¬ CA j + 1/ Ci = |key = i|Huo Hongweounting-sort exampleLoop2123451234A:C:B:for j ¬ 1 to ndo CA j ¬ CA j + 1/ Ci = |key = i|Huo Hongwei19101141343Counting-sort exampleLoop2123451234A:C:B:for j ¬

17、1 to ndo CA j ¬ CA j + 1/ Ci = |key = i|Huo Hongwei20101241343Counting-sort exampleLoop2123451234A:C:B:for j ¬ 1 to ndo CA j ¬ CA j + 1/ Ci = |key = i|Huo Hongwei21102241343Counting-sort exampleLoop3123451234A:C:B:C':for i ¬ 2 to kdo Ci ¬ Ci + Ci1/ Ci = |key £ i|Huo

18、 Hongwei221122102241343Counting-sort exampleLoop3123451234A:C:B:C':for i ¬ 2 to kdo Ci ¬ Ci + Ci1/ Ci = |key £ i|Huo Hongwei231132102241343Counting-sort exampleLoop3123451234A:C:B:C':for i ¬ 2 to kdo Ci ¬ Ci + Ci1/ Ci = |key £ i|Huo Hongwei241135102241343Countin

19、g-sort exampleLoop4123451234A:C:B:C':for j ¬ n downto 1do BCA j ¬ A jCA j ¬ CA j 1Huo Hongwei2511253113541343Counting-sort exampleLoop4123451234A:C:B:C':for j ¬ n downto 1do BCA j ¬ A jCA j ¬ CA j 1Huo Hongwei26112434112541343Counting-sort exampleLoop4123451234A

20、:C:B:C':for j ¬ n downto 1do BCA j ¬ A jCA j ¬ CA j 1Huo Hongwei271114334112441343Counting-sort exampleLoop4123451234A:C:B:C':for j ¬ n downto 1do BCA j ¬ A jCA j ¬ CA j 1Huo Hongwei2801141334111441343Counting-sort exampleLoop4123451234A:C:B:C':for j ¬

21、n downto 1do BCA j ¬ A jCA j ¬ CA j 1Huo Hongwei29011313344011441343AnalysisThe overall time is Q(k+n)Huo Hongwei30COUNTING SORTCOUNTING-SORT(A, B, k)1 for i ¬ 1 to kQ(k)2 do Ci ¬ 03 for j ¬ 1 to lengthAQ(n)4do CAj ¬ CAj+15 /Ci now contains the number of elements equal

22、to i.6 for i ¬ 1 to kQ(k)7do Ci ¬ Ci+ Ci-18 /Ci now contains the number of elements less than or equal to i.9 for j ¬ lengthA downto 110do BCAj ¬ AjQ(n)11CAj ¬ CAj-1Running timeIf k = O(n), then counting sort takes Q(n) time. But, sorting takes W(n lg n) time! Wheres the fal

23、lacy?Answer: Comparison sorting takes W(n lg n) time. Counting sort is not a comparison sort. In fact, not a single comparison between elements occurs!Huo Hongwei31Stable sortingCounting sort is a stable sort: it preserves the input order among equal elements.A:B:Exercise: What other sorts have this

24、 property?Huo Hongwei321334441343Punched cardsPunched card = data record. Hole = value.Algorithm = machine + human operator.Replica of punch card from the 1900 U.S. census.Howells 2000Huo Hongwei33“Modern”cardOne character per column.Produced by the WWW Virtual Punch- Card Server.So, thats why text

25、windows have 80 columns!Huo Hongwei34Origin of radix sortHolleriths original 1889 patent alludes to a most- significant-digit-first radix sort:“The most complicated combinations canily be counted withcomparatively few counters or relays by first assorting the cards according to the first items enter

26、ing into the combinations, then reassorting each group according to the second item entering into the combination, and so on, and finally counting on a few counters the last item of the combination for each group of cards.”Least-significant-digit-first radix sort seems to be a folk invention origina

27、ted by machine operators.Huo Hongwei35Herman Hollerith(1860-1929)The 1880 U.S. Census took almost10 years to process.While a lecturer at MIT, Hollerith prototyped punched-card technology.His machines, including a “card sorter,” allowed the 1890 census total to be reported in 6 weeks.He founded the T

28、abulating Machine Company in 1911, which merged with other companies in 1924 to form International Business Machines.Huo Hongwei36Holleriths tabulating systemFigure from Howells 2000. Pantograph card punch Hand-press Dial counters Sorting boxerHuo Hongwei37Operation of the sorter An operator inserts

29、 a card into the press. Pins on the press reach through the punched holes to make electrical contact with mercury-filled cups beneath the card. Whenever a particular digit value is punched, the lid of the corresponding sorting bin lifts. The operator deposits the cardHollerith Tabulator, Pantograph,

30、 Press, and Sorterinto the bin ands the lid. When all cards have been processed, the front panel is opened, and the cards are collected in order, yielding one pass of a stable sort.Huo Hongwei38Radix sortOrigin: Herman Holleriths card-sorting machine for the1890 U.S. Census.Digit-by-digit sort.Holle

31、riths original (bad) idea: sort on most-significant digit first.Good idea: Sort on least-significant digit first with auxiliary stable sort.Huo Hongwei39Operation of radix sort3 2 94 5 76 5 78 3 94 3 67 2 03 5 57 2 03 5 54 3 64 5 76 5 73 2 98 3 97 2 03 2 94 3 68 3 93 5 54 5 76 5 73 2 93 5 54 3 64 5

32、76 5 77 2 08 3 9Huo Hongwei40Correctness of radix sortInduction on digit position Assume that the numbers are sorted by their low-order t 1 digits.7 2 03 2 94 3 68 3 93 5 54 5 76 5 73 2 93 5 54 3 64 5 76 5 77 2 08 3 9 Sort on digit tHuo Hongwei41Correctness of radix sortInduction on digit position A

33、ssume that the numbers are sorted by their low-order t 1 digits.7 2 03 2 94 3 68 3 93 5 54 5 76 5 73 2 93 5 54 3 64 5 76 5 77 2 08 3 9 Sort on digit t§ Two numbers that differ in digit t are correctly sorted.Huo Hongwei42Correctness of radix sortInduction on digit position Assume that the numbe

34、rs are sorted by their low-order t 1 digits.7 2 03 2 94 3 68 3 93 5 54 5 76 5 73 2 93 5 54 3 64 5 76 5 77 2 08 3 9 Sort on digit t§ Two numbers that differ in digit t are correctly sorted.§ Two numbers equal in digit t are put in the same order as the input Þ correct order.Huo Hongwei

35、43Analysis of radix sortAssume counting sort is the auxiliary stable sort. Sort n computer words of b bits each.Each word can be viewed as having b/r base-2r digits.8888Example 32-bit word r = 8 Þ b/r = 4 passes of counting sort on base-28 digits; or r = 16 Þ b/r = 2 passes of counting sor

36、t on base-216 digits.How many passes should we make?Huo Hongwei44Analysis (continued)Recall: Counting sort takes Q(n + k) time to sort nnumbers in the range from 0 to k 1.If each b-bit word is broken into r-bit pieces, each pass of counting sort takes Q(n + 2r) time. Since there are b/r passes, we h

37、aveT(n, b) = (b/r)(n + 2r)Choose r to minimize T(n, b): Increasing r means fewer passes, but as r >>time grows exponentially.lg n, theHuo Hongwei45Choosing rMinimize T(n, b) by differentiating and setting to 0.Or, just observe that we dont want 2r >>n, and theres no harm asymptotically i

38、n choosing r as large as possible subject to this constraint.Choosing r = lg n implies T(n, b) = Q(b n/lg n). For numbers in the range from 0 to nd 1, we have b = dlg n Þ radix sort runs in Q(d n) time.Huo Hongwei46sIn practice, radix sort is fast for large inputs, as well as simple to code and

39、 maintain.Example (32-bit numbers): At most 3 passes when sorting ³ 2000 numbers. Merge sort and quicksort do at least élg 2000ù = 11passes.Downside: Cant sort in place using counting sort. Also, Unlike quicksort, radix sort displays little locality of reference, and thus a well-tuned

40、 quicksort fares better sometimes on modern processors, with steep memory hierarchies.Huo Hongwei47Appendix: Punched-card technologyHerman Hollerith (1860-1929) 利用凿孔把字母人Punched cards在卡片上编码的式(以发明Herman Hollerith 命名 1860-1929)Holleriths tabulating system Operation of the sorterOrigin of radix sort“Mod

41、ern”cardWeb resources on punched-card technologyHuo Hongwei48Web resources on punched-card technologyDoug Joness punched card index Biography of Herman Hollerith The 1890 U.S. CensusEarly history ofPictures of Holleriths inventionsHolleriths patent application (borrowed from Bells CyberMuseum)Impact

42、 of punched cards on U.S. historyGordonHuo Hongwei49Bucket SortLike counting sort, bucket sort is fast because it assumes something about the input. Whereas counting sort assumes that the input consists of integers in a small range, bucket sort assumes that the input is generated by a random process

43、 that distributes elements uniformly.Idea of Bucket Sort Divide the interval 0,1) into n equal-sized subintervals, or bucket, and then distribute the n input number into the buckets.Huo Hongwei50Bucket SortAssume that all the input is generated by a random process that distributes elements uniform o

44、ver the interval 0,1)Bucket sort 1 Allocate a bucket for each value of the key» That is, insert Ai into list BënAiû 2 For each bucket,» sort list Bi with insertion sort 3 concatenate the list B0, B1, , Bn-1 together in orderHuo Hongwei51Bucket Sort ExampleA=(0.5, 0.1, 0.3, 0.4, 0.3, 0.2, 0.1, 0.1, 0.5, 0.4, 0.5)Sorted list:0.1, 0.1, 0.1, 0.2, 0.3, 0.3,0.4, 0.4, 0.5, 0.5, 0.5Huo Hongwei52bucket in arrayB10.1, 0.1, 0.1B20.2B30.3, 0.3B40.4, 0.4B50.5, 0.5, 0.5Bucket Sort Al