《排序集合和选择》由会员分享，可在线阅读，更多相关《排序集合和选择（61页珍藏版）》请在金锄头文库上搜索。
1、Merge Sort7 2 9 4 2 4 7 97 2 2 79 4 4 97 72 29 94 41Chapter 4Outline and ReadingDivide-and-conquer paradigm, MergeSort (4.1)Sets (4.2);Generic Merging and set operations (4.2.1)nNote: Sections 4.2.2 and 4.2.3 are OptionalQuick-sort (4.3)Analysis of quick-sort (4.3.1)A Lower Bound on Comparison-based
2、 Sorting (4.4)QuickSort and Radix Sort (4.5)In-place quick-sort (4.8)Comparison of Sorting Algorithm (4.6)Selection (4.7)2Chapter 4Divide-and-ConquerDivide-and conquer is a general algorithm design paradigm:nDivide: divide the input data S in two disjoint subsets S1 and S2nRecur: solve the subproble
3、ms associated with S1 and S2nConquer: combine the solutions for S1 and S2 into a solution for SThe base case for the recursion are subproblems of size 0 or 1Merge-sort is a sorting algorithm based on the divide-and-conquer paradigm Like heap-sortnIt uses a comparatornIt has O(n log n) running timeUn
4、like heap-sortnIt does not use an auxiliary priority queuenIt accesses data in a sequential manner (suitable to sort data on a disk)3Chapter 4Merge-SortMerge-sort on an input sequence S with n elements consists of three steps:nDivide: partition S into two sequences S1 and S2 of about n/2 elements ea
5、chnRecur: recursively sort S1 and S2nConquer: merge S1 and S2 into a unique sorted sequenceAlgorithm mergeSort(S, C)Input sequence S with n elements, comparator C Output sequence S sortedaccording to Cif S.size() 1(S1, S2) partition(S, n/2) mergeSort(S1, C)mergeSort(S2, C)S merge(S1, S2)4Chapter 4Me
6、rging Two Sorted SequencesThe conquer step of merge-sort consists of merging two sorted sequences A and B into a sorted sequence S containing the union of the elements of A and BMerging two sorted sequences, each with n/2 elements and implemented by means of a doubly linked list, takes O(n) timeAlgo
7、rithm merge(A, B)Input sequences A and B with n/2 elements each Output sorted sequence of A BS empty sequencewhile A.isEmpty() B.isEmpty()if A.first().element() B.first().element()S.insertLast(A.remove(A.first()elseS.insertLast(B.remove(B.first()while A.isEmpty()S.insertLast(A.remove(A.first()while
8、B.isEmpty()S.insertLast(B.remove(B.first()return S5Chapter 4Merge-Sort TreeAn execution of merge-sort is depicted by a binary treeneach node represents a recursive call of merge-sort and storeswunsorted sequence before the execution and its partitionwsorted sequence at the end of the executionnthe r
9、oot is the initial call nthe leaves are calls on subsequences of size 0 or 17 2 9 4 2 4 7 97 2 2 79 4 4 97 72 29 94 46Chapter 4Execution ExamplePartition7 2 9 4 2 4 7 93 8 6 1 1 3 8 67 2 2 79 4 4 93 8 3 86 1 1 67 72 29 94 43 38 86 61 17 2 9 4 3 8 6 1 1 2 3 4 6 7 8 97Chapter 4Execution Example (cont.
10、)Recursive call, partition 7 2 9 4 2 4 7 93 8 6 1 1 3 8 67 2 2 79 4 4 93 8 3 86 1 1 67 72 29 94 43 38 86 61 17 2 9 4 3 8 6 1 1 2 3 4 6 7 8 98Chapter 4Execution Example (cont.)Recursive call, partition 7 2 9 4 2 4 7 93 8 6 1 1 3 8 67 2 2 79 4 4 93 8 3 86 1 1 67 72 29 94 43 38 86 61 17 2 9 4 3 8 6 1 1
11、 2 3 4 6 7 8 99Chapter 4Execution Example (cont.)Recursive call, base case 7 2 9 4 2 4 7 93 8 6 1 1 3 8 67 2 2 79 4 4 93 8 3 86 1 1 67 72 29 94 43 38 86 61 17 2 9 4 3 8 6 1 1 2 3 4 6 7 8 910Chapter 4Execution Example (cont.)Recursive call, base case 7 2 9 4 2 4 7 93 8 6 1 1 3 8 67 2 2 79 4 4 93 8 3
12、86 1 1 67 72 29 94 43 38 86 61 17 2 9 4 3 8 6 1 1 2 3 4 6 7 8 911Chapter 4Execution Example (cont.)Merge 7 2 9 4 2 4 7 93 8 6 1 1 3 8 67 2 2 79 4 4 93 8 3 86 1 1 67 72 29 94 43 38 86 61 17 2 9 4 3 8 6 1 1 2 3 4 6 7 8 912Chapter 4Execution Example (cont.)Recursive call, , base case, merge 7 2 9 4 2 4
13、 7 93 8 6 1 1 3 8 67 2 2 79 4 4 93 8 3 86 1 1 67 72 23 38 86 61 17 2 9 4 3 8 6 1 1 2 3 4 6 7 8 99 94 413Chapter 4Execution Example (cont.)Merge 7 2 9 4 2 4 7 93 8 6 1 1 3 8 67 2 2 79 4 4 93 8 3 86 1 1 67 72 29 94 43 38 86 61 17 2 9 4 3 8 6 1 1 2 3 4 6 7 8 914Chapter 4Execution Example (cont.)Recursi
14、ve call, , merge, merge 7 2 9 4 2 4 7 93 8 6 1 1 3 6 87 2 2 79 4 4 93 8 3 86 1 1 67 72 29 94 43 38 86 61 17 2 9 4 3 8 6 1 1 2 3 4 6 7 8 915Chapter 4Execution Example (cont.)Merge 7 2 9 4 2 4 7 93 8 6 1 1 3 6 87 2 2 79 4 4 93 8 3 86 1 1 67 72 29 94 43 38 86 61 17 2 9 4 3 8 6 1 1 2 3 4 6 7 8 916Chapte
15、r 4Analysis of Merge-SortThe height h of the merge-sort tree is O(log n) nat each recursive call we divide in half the sequence, The overall amount or work done at the nodes of depth i is O(n) nwe partition and merge 2i sequences of size n/ /2i nwe make 2i+1 recursive callsThus, the total running ti
16、me of merge-sort is O(n log n)depth #seqssize01n12n/ /2i2in/ /2i17Chapter 4Sets18Chapter 4Set OperationsWe represent a set by the sorted sequence of its elementsBy specializing the auxliliary methods he generic merge algorithm can be used to perform basic set operations:nunionnintersectionnsubtracti
17、onThe running time of an operation on sets A and B should be at most O(nA + nB)Set union:naIsLess(a, S)S.insertFirst(a)nbIsLess(b, S)S.insertLast(b)nbothAreEqual(a, b, S)S. insertLast(a)Set intersection:naIsLess(a, S) do nothing nbIsLess(b, S) do nothing nbothAreEqual(a, b, S)S. insertLast(a)19Chapt
18、er 4Storing a Set in a ListWe can implement a set with a listElements are stored sorted according to some canonical orderingThe space used is O(n)ListNodes storing set elements in orderSet elements20Chapter 4Generic MergingGeneralized merge of two sorted lists A and BTemplate method genericMergeAuxi
19、liary methodsnaIsLessnbIsLessnbothAreEqualRuns in O(nA + nB) time provided the auxiliary methods run in O(1) timeAlgorithm genericMerge(A, B)S empty sequencewhile A.isEmpty() B.isEmpty()a A.first().element(); b B.first().element()if a baIsLess(a, S); A.remove(A.first()else if b abIsLess(b, S); B.rem
20、ove(B.first()else b = a bothAreEqual(a, b, S)A.remove(A.first(); B.remove(B.first()while A.isEmpty()aIsLess(a, S); A.remove(A.first()while B.isEmpty()bIsLess(b, S); B.remove(B.first()return S21Chapter 4Using Generic Merge for Set OperationsAny of the set operations can be implemented using a generic
21、 mergeFor example:nFor intersection: only copy elements that are duplicated in both listnFor union: copy every element from both lists except for the duplicatesAll methods run in linear time.22Chapter 4Quick-Sort7 4 9 6 2 2 4 6 7 94 2 2 47 9 7 92 29 923Chapter 4Quick-SortQuick-sort is a randomized s
22、orting algorithm based on the divide-and-conquer paradigm:nDivide: pick a random element x (called pivot) and partition S into wL elements less than xwE elements equal xwG elements greater than xnRecur: sort L and GnConquer: join L, E and GxxLGEx24Chapter 4PartitionWe partition an input sequence as
23、follows:nWe remove, in turn, each element y from S and nWe insert y into L, E or G, depending on the result of the comparison with the pivot xEach insertion and removal is at the beginning or at the end of a sequence, and hence takes O(1) timeThus, the partition step of quick-sort takes O(n) timeAlg
24、orithm partition(S, p)Input sequence S, position p of pivot Output subsequences L, E, G of the elements of S less than, equal to,or greater than the pivot, resp.L, E, G empty sequencesx S.remove(p) while S.isEmpty()y S.remove(S.first()if y x G.insertLast(y)return L, E, G25Chapter 4Quick-Sort TreeAn
25、execution of quick-sort is depicted by a binary treenEach node represents a recursive call of quick-sort and storeswUnsorted sequence before the execution and its pivotwSorted sequence at the end of the executionnThe root is the initial call nThe leaves are calls on subsequences of size 0 or 17 4 9
26、6 2 2 4 6 7 94 2 2 47 9 7 92 29 926Chapter 4Execution ExamplePivot selection7 2 9 4 2 4 7 92 27 2 9 4 3 7 6 1 1 2 3 4 6 7 8 93 8 6 1 1 3 8 63 38 89 4 4 99 94 427Chapter 4Execution Example (cont.)Partition, recursive call, pivot selection 2 4 3 1 2 4 7 99 4 4 99 94 47 2 9 4 3 7 6 1 1 2 3 4 6 7 8 93 8
27、 6 1 1 3 8 63 38 82 228Chapter 4Execution Example (cont.)Partition, recursive call, base case 2 4 3 1 2 4 7 1 19 4 4 99 94 47 2 9 4 3 7 6 1 1 2 3 4 6 7 8 93 8 6 1 1 3 8 63 38 829Chapter 4Execution Example (cont.)Recursive call, pivot selection7 9 7 1 1 3 8 68 87 2 9 4 3 7 6 1 1 2 3 4 6 7 8 92 4 3 1
28、1 2 3 41 14 3 3 49 94 49 930Chapter 4Execution Example (cont.)Partition, , recursive call, base case7 9 7 1 1 3 8 68 87 2 9 4 3 7 6 1 1 2 3 4 6 7 8 92 4 3 1 1 2 3 41 14 3 3 49 94 49 931Chapter 4Execution Example (cont.)Join, join7 9 7 17 7 98 87 2 9 4 3 7 6 1 1 2 3 4 6 7 7 92 4 3 1 1 2 3 41 14 3 3 4
29、9 94 49 932Chapter 4Worst-case Running TimeThe worst case for quick-sort occurs when the pivot is the unique minimum or maximum elementOne of L and G has size n - 1 and the other has size 0The running time is proportional to the sumn + (n - 1) + + 2 + 1Thus, the worst-case running time of quick-sort
30、 is O(n2)depth time0n1n - 1n - 1133Chapter 4Expected Running TimeConsider a recursive call of quick-sort on a sequence of size snGood call: the sizes of L and G are each less than 3s/4nBad call: one of L and G has size greater than 3s/4A call is good with probability 1/2n1/2 of the possible pivots c
31、ause good calls:7 9 7 1 17 2 9 4 3 7 6 1 92 4 3 1 7 2 9 4 3 7 617 2 9 4 3 7 6 1Good callBad call1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16Good pivotsBad pivotsBad pivots34Chapter 4Expected Running Time, Part 2Probabilistic Fact: The expected number of coin tosses required in order to get k heads is 2kFo
32、r a node of depth i, we expectni/2 ancestors are good callsnThe size of the input sequence for the current call is at most (3/4)i/2nTherefore, we havenFor a node of depth 2log4/3n, the expected input size is onenThe expected height of the quick-sort tree is O(log n)The amount or work done at the nod
33、es of the same depth is O(n)Thus, the expected running time of quick-sort is O(n log n)35Chapter 4In-Place Quick-SortQuick-sort can be implemented to run in-placeIn the partition step, we use replace operations to rearrange the elements of the input sequence such thatnthe elements less than the pivo
34、t have rank less than hnthe elements equal to the pivot have rank between h and knthe elements greater than the pivot have rank greater than kThe recursive calls considernelements with rank less than hnelements with rank greater than kAlgorithm inPlaceQuickSort(S, l, r)Input sequence S, ranks l and
35、rOutput sequence S with theelements of rank between l and rrearranged in increasing order if l r returni a random integer between l and r x S.elemAtRank(i) (h, k) inPlacePartition(x)inPlaceQuickSort(S, l, h - 1)inPlaceQuickSort(S, k + 1, r)36Chapter 4In-Place PartitioningPerform the partition using
36、two indices to split S into L and E U G (a similar method can split E U G into E and G).Repeat until j and k cross:nScan j to the right until finding an element x.nScan k to the left until finding an element x.nSwap elements at indices j and k3 2 5 1 0 7 3 5 9 2 7 9 8 9 7 6 9jk(pivot = 6)3 2 5 1 0 7
37、 3 5 9 2 7 9 8 9 7 6 9jk37Chapter 4Execution Example (cont.)Recursive call, , base case, join3 8 6 1 1 3 8 63 38 87 2 9 4 3 7 6 1 1 2 3 4 6 7 8 92 4 3 1 1 2 3 41 14 3 3 49 94 438Chapter 4A Lower Bound on Comparison-based Sorting (4.4)39Chapter 4Comparison-Based SortingMany sorting algorithms are com
38、parison based.nThey sort by making comparisons between pairs of objectsnExamples: bubble-sort, selection-sort, insertion-sort, heap-sort, merge-sort, quick-sort, .Let us therefore derive a lower bound on the running time of any algorithm that uses comparisons to sort n elements, x1, x2, , xn.Is xi x
39、j?yesno40Chapter 4Counting ComparisonsLet us just count comparisons then.Each possible run of the algorithm corresponds to a root-to-leaf path in a decision tree41Chapter 4Decision Tree HeightThe height of this decision tree is a lower bound on the running timeEvery possible input permutation must l
40、ead to a separate leaf output. nIf not, some input 45 would have same output ordering as 54, which would be wrong.Since there are n!=1*2*n leaves, the height is at least log (n!)42Chapter 4The Lower BoundAny comparison-based sorting algorithms takes at least log (n!) timeTherefore, any such algorith
41、m takes time at leastThat is, any comparison-based sorting algorithm must run in (n log n) time.43Chapter 4Bucket-Sort and Radix-Sort0123456789B1, c7, d7, g3, b3, a7, e 44Chapter 4Bucket-Sort ( 4.5.1)Let be S be a sequence of n (key, element) items with keys in the range 0, N - 1Bucket-sort uses the
42、 keys as indices into an auxiliary array B of sequences (buckets)Phase 1: Empty sequence S by moving each item (k, o) into its bucket BkPhase 2: For i = 0, , N - 1, move the items of bucket Bi to the end of sequence SAnalysis:nPhase 1 takes O(n) timenPhase 2 takes O(n + N) timeBucket-sort takes O(n
43、+ N) time Algorithm bucketSort(S, N)Input sequence S of (key, element)items with keys in the range0, N - 1Output sequence S sorted byincreasing keysB array of N empty sequenceswhile S.isEmpty()f S.first()(k, o) S.remove(f)Bk.insertLast(k, o)for i 0 to N - 1while Bi.isEmpty() f Bi.first()(k, o) Bi.re
44、move(f)S.insertLast(k, o)45Chapter 4ExampleKey range 0, 97, d1, c3, a7, g3, b7, e1, c3, a3, b7, d7, g7, ePhase 1Phase 20123456789B1, c7, d7, g3, b3, a7, e46Chapter 4Properties and ExtensionsKey-type PropertynThe keys are used as indices into an array and cannot be arbitrary objectsnNo external compa
45、ratorStable Sort PropertynThe relative order of any two items with the same key is preserved after the execution of the algorithmExtensionsnInteger keys in the range a, bwPut item (k, o) into bucketBk - a nString keys from a set D of possible strings, where D has constant size (e.g., names of the 50
46、 U.S. states)wSort D and compute the rank r(k) of each string k of D in the sorted sequence wPut item (k, o) into bucket Br(k)47Chapter 4Lexicographic OrderA d-tuple is a sequence of d keys (k1, k2, , kd), where key ki is said to be the i-th dimension of the tupleExample:nThe Cartesian coordinates o
47、f a point in space are a 3-tupleThe lexicographic order of two d-tuples is recursively defined as follows(x1, x2, , xd) (y1, y2, , yd)x1 y1 x1 = y1 (x2, , xd) (y2, , yd)I.e., the tuples are compared by the first dimension, then by the second dimension, etc.48Chapter 4Lexicographic-SortLet Ci be the
48、comparator that compares two tuples by their i-th dimensionLet stableSort(S, C) be a stable sorting algorithm that uses comparator CLexicographic-sort sorts a sequence of d-tuples in lexicographic order by executing d times algorithm stableSort, one per dimensionLexicographic-sort runs in O(dT(n) ti
49、me, where T(n) is the running time of stableSort Algorithm lexicographicSort(S)Input sequence S of d-tuplesOutput sequence S sorted inlexicographic orderfor i d downto 1stableSort(S, Ci)Example:(7,4,6) (5,1,5) (2,4,6) (2, 1, 4) (3, 2, 4)(2, 1, 4) (3, 2, 4) (5,1,5) (7,4,6) (2,4,6)(2, 1, 4) (5,1,5) (3
50、, 2, 4) (7,4,6) (2,4,6)(2, 1, 4) (2,4,6) (3, 2, 4) (5,1,5) (7,4,6)49Chapter 4Radix-Sort ( 4.5.2)Radix-sort is a specialization of lexicographic-sort that uses bucket-sort as the stable sorting algorithm in each dimensionRadix-sort is applicable to tuples where the keys in each dimension i are intege
51、rs in the range 0, N - 1Radix-sort runs in time O(d( n + N)Algorithm radixSort(S, N)Input sequence S of d-tuples suchthat (0, , 0) (x1, , xd) and(x1, , xd) (N - 1, , N - 1)for each tuple (x1, , xd) in S Output sequence S sorted inlexicographic orderfor i d downto 1bucketSort(S, N)50Chapter 4Radix-So
52、rt for Binary NumbersConsider a sequence of n b-bit integers x = xb - 1 x1x0We represent each element as a b-tuple of integers in the range 0, 1 and apply radix-sort with N = 2This application of the radix-sort algorithm runs in O(bn) time For example, we can sort a sequence of 32-bit integers in li
53、near timeAlgorithm binaryRadixSort(S)Input sequence S of b-bitintegers Output sequence S sortedreplace each element xof S with the item (0, x)for i 0 to b - 1replace the key k of each item (k, x) of Swith bit xi of xbucketSort(S, 2)51Chapter 4ExampleSorting a sequence of 4-bit integers10010010110100
54、0111100010111010011101000110011101000100101110100100010010110111100001001010011101111052Chapter 4Summary of Sorting Algorithms (4.6) AlgorithmTimeNotesselection-sortO(n2)w sloww in-placew for small data sets ( 1K)insertion-sortO(n2)w sloww in-placew for small data sets ( 1M)53Chapter 4Selection (4.7
55、)54Chapter 4The Selection ProblemGiven an integer k and n elements x1, x2, , xn, taken from a total order, find the k-th smallest element in this set.Of course, we can sort the set in O(n log n) time and then index the k-th element.Can we solve the selection problem faster?7 4 9 6 2 2 4 6 7 9k=355Ch
56、apter 4Quick-Select Quick-select is a randomized selection algorithm based on the prune-and-search paradigm:nPrune: pick a random element x (called pivot) and partition S into wL elements less than xwE elements equal xwG elements greater than xnSearch: depending on k, either answer is in E, or we ne
57、ed to recurse in either L or GxxLGEk |L|L| k |L|+|E|k = k - |L| - |E|56Chapter 4PartitionWe partition an input sequence as in the quick-sort algorithm:nWe remove, in turn, each element y from S and nWe insert y into L, E or G, depending on the result of the comparison with the pivot xEach insertion
58、and removal is at the beginning or at the end of a sequence, and hence takes O(1) timeThus, the partition step of quick-select takes O(n) timeAlgorithm partition(S, p)Input sequence S, position p of pivot Output subsequences L, E, G of the elements of S less than, equal to,or greater than the pivot,
59、 resp.L, E, G empty sequencesx S.remove(p) while S.isEmpty()y S.remove(S.first()if y x G.insertLast(y)return L, E, G57Chapter 4Quick-Select VisualizationAn execution of quick-select can be visualized by a recursion pathnEach node represents a recursive call of quick-select, and stores k and the rema
60、ining sequencek=5, S=(7 4 9 3 2 6 5 1 8)5k=2, S=(7 4 9 6 5 8)k=2, S=(7 4 6 5)k=1, S=(7 6 5)58Chapter 4Expected Running TimeConsider a recursive call of quick-select on a sequence of size snGood call: the sizes of L and G are each less than 3s/4nBad call: one of L and G has size greater than 3s/4A ca
61、ll is good with probability 1/2n1/2 of the possible pivots cause good calls:7 9 7 1 17 2 9 4 3 7 6 1 92 4 3 1 7 2 9 4 3 7 617 2 9 4 3 7 6 1Good callBad call1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16Good pivotsBad pivotsBad pivots59Chapter 4Expected Running Time, Part 2Probabilistic Fact #1: The expected
62、 number of coin tosses required in order to get one head is twoProbabilistic Fact #2: Expectation is a linear function:nE(X + Y ) = E(X ) + E(Y )nE(cX ) = cE(X )Let T(n) denote the expected running time of quick-select.By Fact #2,nT(n) T(3n/4) + bn*(expected # of calls before a good call)By Fact #1,
63、nT(n) T(3n/4) + 2bnThat is, T(n) is a geometric series:nT(n) 2bn + 2b(3/4)n + 2b(3/4)2n + 2b(3/4)3n + So T(n) is O(n).We can solve the selection problem in O(n) expected time.60Chapter 4Deterministic Selection We can do selection in O(n) worst-case time.Main idea: recursively use the selection algorithm itself to find a good pivot for quick-select:nDivide S into n/5 sets of 5 eachnFind a median in each setnRecursively find the median of the “baby” medians. See Exercise C-4.24 for details of analysis.1234512345123451234512345123451234512345123451234512345Min sizefor LMin sizefor G61Chapter 4
