Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 29
Текст из файла (страница 29)
In a recursiontree for an average-case execution of PARTITION, the good and bad splits are distributedrandomly throughout the tree. Suppose for the sake of intuition, however, that the good andbad splits alternate levels in the tree, and that the good splits are best-case splits and the badsplits are worst-case splits. Figure 7.5(a) shows the splits at two consecutive levels in therecursion tree. At the root of the tree, the cost is n for partitioning, and the subarrays producedhave sizes n - 1 and 0: the worst case. At the next level, the subarray of size n - 1 is best-casepartitioned into subarrays of size (n - 1)/2 - 1 and (n - 1)/2. Let's assume that the boundarycondition cost is 1 for the subarray of size 0.Figure 7.5: (a) Two levels of a recursion tree for quicksort. The partitioning at the root costs nand produces a "bad" split: two subarrays of sizes 0 and n - 1.
The partitioning of the subarrayof size n - 1 costs n - 1 and produces a "good" split: subarrays of size (n - 1)/2 - 1 and (n -1)/2. (b) A single level of a recursion tree that is very well balanced. In both parts, thepartitioning cost for the subproblems shown with elliptical shading is Θ(n). Yet thesubproblems remaining to be solved in (a), shown with square shading, are no larger than thecorresponding subproblems remaining to be solved in (b).The combination of the bad split followed by the good split produces three subarrays of sizes0, (n - 1)/2 - 1, and (n - 1)/2 at a combined partitioning cost of Θ(n) + Θ(n - 1) = Θ(n).Certainly, this situation is no worse than that in Figure 7.5(b), namely a single level ofpartitioning that produces two subarrays of size (n - 1)/2, at a cost of Θ(n).
Yet this lattersituation is balanced! Intuitively, the Θ(n - 1) cost of the bad split can be absorbed into theΘ(n) cost of the good split, and the resulting split is good. Thus, the running time of quicksort,when levels alternate between good and bad splits, is like the running time for good splitsalone: still O(n lg n), but with a slightly larger constant hidden by the O-notation. We shallgive a rigorous analysis of the average case in Section 7.4.2.Exercises 7.2-1Use the substitution method to prove that the recurrence T (n) = T (n - 1) + Θ(n) has thesolution T (n) = Θ(n2), as claimed at the beginning of Section 7.2.Exercises 7.2-2What is the running time of QUICKSORT when all elements of array A have the same value?Exercises 7.2-3Show that the running time of QUICKSORT is Θ(n2) when the array A contains distinctelements and is sorted in decreasing order.Exercises 7.2-4Banks often record transactions on an account in order of the times of the transactions, butmany people like to receive their bank statements with checks listed in order by checknumber.
People usually write checks in order by check number, and merchants usually cashthem with reasonable dispatch. The problem of converting time-of-transaction ordering tocheck-number ordering is therefore the problem of sorting almost-sorted input.
Argue that theprocedure INSERTION-SORT would tend to beat the procedure QUICKSORT on thisproblem.Exercises 7.2-5Suppose that the splits at every level of quicksort are in the proportion 1 - α to α, where 0 < α≤ 1/2 is a constant. Show that the minimum depth of a leaf in the recursion tree isapproximately - lg n/ lg α and the maximum depth is approximately -lg n/ lg(1 - α). (Don'tworry about integer round-off.)Exercises 7.2-6: ⋆Argue that for any constant 0 < α ≤ 1/2, the probability is approximately 1 - 2α that on arandom input array, PARTITION produces a split more balanced than 1-α to α.7.3 A randomized version of quicksortIn exploring the average-case behavior of quicksort, we have made an assumption that allpermutations of the input numbers are equally likely.
In an engineering situation, however, wecannot always expect it to hold. (See Exercise 7.2-4.) As we saw in Section 5.3, we cansometimes add randomization to an algorithm in order to obtain good average-caseperformance over all inputs. Many people regard the resulting randomized version ofquicksort as the sorting algorithm of choice for large enough inputs.In Section 5.3, we randomized our algorithm by explicitly permuting the input. We could doso for quicksort also, but a different randomization technique, called random sampling, yieldsa simpler analysis. Instead of always using A[r] as the pivot, we will use a randomly chosenelement from the subarray A[p r]. We do so by exchanging element A[r] with an elementchosen at random from A[p r].
This modification, in which we randomly sample the rangep,...,r, ensures that the pivot element x = A[r] is equally likely to be any of the r - p + 1elements in the subarray. Because the pivot element is randomly chosen, we expect the splitof the input array to be reasonably well balanced on average.The changes to PARTITION and QUICKSORT are small. In the new partition procedure, wesimply implement the swap before actually partitioning:RANDOMIZED-PARTITION(A, p, r)1 i ← RANDOM(p, r)2 exchange A[r] ↔ A[i]3 return PARTITION(A, p, r)The new quicksort calls RANDOMIZED-PARTITION in place of PARTITION:RANDOMIZED-QUICKSORT(A, p, r)1 if p < r2then q ← RANDOMIZED-PARTITION(A, p, r)3RANDOMIZED-QUICKSORT(A, p, q - 1)4RANDOMIZED-QUICKSORT(A, q + 1, r)We analyze this algorithm in the next section.Exercises 7.3-1Why do we analyze the average-case performance of a randomized algorithm and not itsworst-case performance?Exercises 7.3-2During the running of the procedure RANDOMIZED-QUICKSORT, how many calls aremade to the random-number generator RANDOM in the worst case? How about in the bestcase? Give your answer in terms of Θ-notation.7.4 Analysis of quicksortSection 7.2 gave some intuition for the worst-case behavior of quicksort and for why weexpect it to run quickly.
In this section, we analyze the behavior of quicksort more rigorously.We begin with a worst-case analysis, which applies to either QUICKSORT orRANDOMIZED-QUICKSORT, and conclude with an average-case analysis ofRANDOMIZED-QUICKSORT.7.4.1 Worst-case analysisWe saw in Section 7.2 that a worst-case split at every level of recursion in quicksort producesa Θ(n2) running time, which, intuitively, is the worst-case running time of the algorithm.
Wenow prove this assertion.Using the substitution method (see Section 4.1), we can show that the running time ofquicksort is O(n2). Let T (n) be the worst-case time for the procedure QUICKSORT on aninput of size n. We have the recurrence(7.1)where the parameter q ranges from 0 to n - 1 because the procedure PARTITION producestwo subproblems with total size n - 1. We guess that T (n) ≤ cn2 for some constant c.Substituting this guess into recurrence (7.1), we obtainThe expression q2 +(n-q-1)2 achieves a maximum over the parameter's range 0 ≤ q ≤ n - 1 ateither endpoint, as can be seen since the second derivative of the expression with respect to qis positive (see Exercise 7.4-3). This observation gives us the bound max≤q≤n-1(q2+ (n - q - 1)2)≤ (n - 1)2 = n2 - 2n + 1.
Continuing with our bounding of T (n), we obtainT(n) ≤ cn2 - c(2n - 1) + Θ(n)≤ cn2,since we can pick the constant c large enough so that the c(2n - 1) term dominates the Θ(n)term. Thus, T (n) = O(n2). We saw in Section 7.2 a specific case in which quicksort takesΘ(n2) time: when partitioning is unbalanced. Alternatively, Exercise 7.4-1 asks you to showthat recurrence (7.1) has a solution of T (n) = Θ(n2). Thus, the (worst-case) running time ofquicksort is Θ(n2).7.4.2 Expected running timeWe have already given an intuitive argument why the average-case running time ofRANDOMIZED-QUICKSORT is O(n lg n): if, in each level of recursion, the split induced byRANDOMIZED-PARTITION puts any constant fraction of the elements on one side of thepartition, then the recursion tree has depth Θ(lg n), and O(n) work is performed at each level.Even if we add new levels with the most unbalanced split possible between these levels, thetotal time remains O(n lg n).
We can analyze the expected running time of RANDOMIZEDQUICKSORT precisely by first understanding how the partitioning procedure operates andthen using this understanding to derive an O(n lg n) bound on the expected running time. Thisupper bound on the expected running time, combined with the Θ(n lg n) best-case bound wesaw in Section 7.2, yields a Θ(n lg n) expected running time.Running time and comparisonsThe running time of QUICKSORT is dominated by the time spent in the PARTITIONprocedure.
Each time the PARTITION procedure is called, a pivot element is selected, andthis element is never included in any future recursive calls to QUICK-SORT andPARTITION. Thus, there can be at most n calls to PARTITION over the entire execution ofthe quicksort algorithm. One call to PARTITION takes O(1) time plus an amount of time thatis proportional to the number of iterations of the for loop in lines 3-6. Each iteration of thisfor loop performs a comparison inline 4, comparing the pivot element to another element ofthe array A. Therefore, if we can count the total number of times that line 4 is executed, wecan bound the total time spent in the for loop during the entire execution of QUICKSORT.Lemma 7.1Let X be the number of comparisons performed in line 4 of PARTITION over the entireexecution of QUICKSORT on an n-element array.
Then the running time of QUICKSORT isO(n + X).Proof By the discussion above, there are n calls to PARTITION, each of which does aconstant amount of work and then executes the for loop some number of times. Each iterationof the for loop executes line 4.Our goal, therefore is to compute X, the total number of comparisons performed in all calls toPARTITION. We will not attempt to analyze how many comparisons are made in each call toPARTITION. Rather, we will derive an overall bound on the total number of comparisons.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
