Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 31
Текст из файла (страница 31)
Describe a scenario in which the stack depth of QUICKSORT' is Θ(n) on an n-elementinput array.c. Modify the code for QUICKSORT' so that the worst-case stack depth is Θ(lg n).Maintain the O(n lg n) expected running time of the algorithm.Problems 7-5: Median-of-3 partitionOne way to improve the RANDOMIZED-QUICKSORT procedure is to partition around apivot that is chosen more carefully than by picking a random element from the subarray.
Onecommon approach is the median-of-3 method: choose the pivot as the median (middleelement) of a set of 3 elements randomly selected from the subarray. (See Exercise 7.4-6.) Forthis problem, let us assume that the elements in the input array A[1 n] are distinct and that n≥ 3. We denote the sorted output array by A'[1 n]. Using the median-of-3 method to choosethe pivot element x, define pi = Pr{x = A'[i]}.a.
Give an exact formula for pi as a function of n and i for i = 2, 3,..., n - 1. (Note that p1= pn = 0.)b. By what amount have we increased the likelihood of choosing the pivot as x = A'[⌊(n+ 1/2⌋], the median of A[1 n], compared to the ordinary implementation? Assumethat n → ∞, and give the limiting ratio of these probabilities.c. If we define a "good" split to mean choosing the pivot as x = A'[i], where n/ ≤ i ≤ 2n/3,by what amount have we increased the likelihood of getting a good split compared tothe ordinary implementation? (Hint: Approximate the sum by an integral.)d.
Argue that in the Ω(n lg n) running time of quicksort, the median-of-3 method affectsonly the constant factor.Problems 7-6: Fuzzy sorting of intervalsConsider a sorting problem in which the numbers are not known exactly. Instead, for eachnumber, we know an interval on the real line to which it belongs. That is, we are given nclosed intervals of the form [ai, bi], where ai ≤ bi. The goal is to fuzzy-sort these intervals, i.e.,produce a permutation i1, i2,..., in of the intervals such that there exist, satisfyingc1 ≤ c2 ≤ ··· ≤ cn.a. Design an algorithm for fuzzy-sorting n intervals.
Your algorithm should have thegeneral structure of an algorithm that quicksorts the left endpoints (the ai 's), but itshould take advantage of overlapping intervals to improve the running time. (As theintervals overlap more and more, the problem of fuzzy-sorting the intervals gets easierand easier.
Your algorithm should take advantage of such overlapping, to the extentthat it exists.)b. Argue that your algorithm runs in expected time Θ(n lg n) in general, but runs inexpected time Θ(n) when all of the intervals overlap (i.e., when there exists a value xsuch that x [ai, bi] for all i). Your algorithm should not be checking for this caseexplicitly; rather, its performance should naturally improve as the amount of overlapincreases.Chapter NotesThe quicksort procedure was invented by Hoare [147]; Hoare's version appears in Problem 71. The PARTITION procedure given in Section 7.1 is due to N. Lomuto. The analysis inSection 7.4 is due to Avrim Blum.
Sedgewick [268] and Bentley [40] provide a goodreference on the details of implementation and how they matter.McIlroy [216] showed how to engineer a "killer adversary" that produces an array on whichvirtually any implementation of quicksort takes Θ(n2) time. If the implementation israndomized, the adversary produces the array after seeing the random choices of the quicksortalgorithm.Chapter 8: Sorting in Linear TimeOverviewWe have now introduced several algorithms that can sort n numbers in O(n lg n) time. Mergesort and heapsort achieve this upper bound in the worst case; quicksort achieves it on average.Moreover, for each of these algorithms, we can produce a sequence of n input numbers thatcauses the algorithm to run in Θ(n lg n) time.These algorithms share an interesting property: the sorted order they determine is based onlyon comparisons between the input elements. We call such sorting algorithms comparisonsorts.
All the sorting algorithms introduced thus far are comparison sorts.In Section 8.1, we shall prove that any comparison sort must make Θ(n lg n) comparisons inthe worst case to sort n elements. Thus, merge sort and heapsort are asymptotically optimal,and no comparison sort exists that is faster by more than a constant factor.Sections 8.2, 8.3, and 8.4 examine three sorting algorithms-counting sort, radix sort, andbucket sort-that run in linear time. Needless to say, these algorithms use operations other thancomparisons to determine the sorted order. Consequently, the Θ(n lg n) lower bound does notapply to them.8.1 Lower bounds for sortingIn a comparison sort, we use only comparisons between elements to gain order informationabout an input sequence a1, a2, . .
., an . That is, given two elements ai and aj, we performone of the tests ai < aj, ai ≤ aj, ai = aj, ai ≥ aj, or ai > aj to determine their relative order. Wemay not inspect the values of the elements or gain order information about them in any otherway.In this section, we assume without loss of generality that all of the input elements are distinct.Given this assumption, comparisons of the form ai = aj are useless, so we can assume that nocomparisons of this form are made. We also note that the comparisons ai ≤ aj, ai ≥ aj, ai > aj,and ai < aj are all equivalent in that they yield identical information about the relative order ofai and aj.
We therefore assume that all comparisons have the form ai ≤ aj.The decision-tree modelComparison sorts can be viewed abstractly in terms of decision trees. A decision tree is a fullbinary tree that represents the comparisons between elements that are performed by aparticular sorting algorithm operating on an input of a given size. Control, data movement,and all other aspects of the algorithm are ignored.
Figure 8.1 shows the decision treecorresponding to the insertion sort algorithm from Section 2.1 operating on an input sequenceof three elements.Figure 8.1: The decision tree for insertion sort operating on three elements. An internal nodeannotated by i: j indicates a comparison between ai and aj. A leaf annotated by thepermutation π(1), π(2), .
. ., π(n) indicates the ordering aπ(1) ≤ aπ(2) ≤ ··· aπ(n). The shadedpath indicates the decisions made when sorting the input sequence a1 = 6, a2 = 8, a3 = 5the permutation 3, 1, 2 at the leaf indicates that the sorted ordering is a3 = 5 a1 = 6 a2 = 8.There are 3! = 6 possible permutations of the input elements, so the decision tree must have atleast 6 leaves.In a decision tree, each internal node is annotated by i: j for some i and j in the range 1 ≤ i, j n,where n is the number of elements in the input sequence.
Each leaf is annotated by apermutation π(1), π(2), . . ., π(n) . (See Section C.1 for background on permutations.) Theexecution of the sorting algorithm corresponds to tracing a path from the root of the decisiontree to a leaf. At each internal node, a comparison ai aj is made. The left subtree then dictatessubsequent comparisons for ai aj, and the right subtree dictates subsequent comparisons for ai> aj.
When we come to a leaf, the sorting algorithm has established the ordering aπ(1) aπ(2) ···aπ(n). Because any correct sorting algorithm must be able to produce each permutation of itsinput, a necessary condition for a comparison sort to be correct is that each of the n!permutations on n elements must appear as one of the leaves of the decision tree, and thateach of these leaves must be reachable from the root by a path corresponding to an actualexecution of the comparison sort. (We shall refer to such leaves as "reachable.") Thus, weshall consider only decision trees in which each permutation appears as a reachable leaf.A lower bound for the worst caseThe length of the longest path from the root of a decision tree to any of its reachable leavesrepresents the worst-case number of comparisons that the corresponding sorting algorithmperforms. Consequently, the worst-case number of comparisons for a given comparison sortalgorithm equals the height of its decision tree.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
