Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 28
Текст из файла (страница 28)
It alsohas the advantage of sorting in place (see page 16), and it works well even in virtual memoryenvironments.Section 7.1 describes the algorithm and an important subroutine used by quicksort forpartitioning. Because the behavior of quicksort is complex, we start with an intuitivediscussion of its performance in Section 7.2 and postpone its precise analysis to the end of thechapter. Section 7.3 presents a version of quicksort that uses random sampling. This algorithmhas a good average-case running time, and no particular input elicits its worst-case behavior.The randomized algorithm is analyzed in Section 7.4, where it is shown to run in Θ(n2) timein the worst case and in O(n lg n) time on average.7.1 Description of quicksortQuicksort, like merge sort, is based on the divide-and-conquer paradigm introduced in Section2.3.1. Here is the three-step divide-and-conquer process for sorting a typical subarray A[pr].•••Divide: Partition (rearrange) the array A[p r] into two (possibly empty) subarraysA[p q - 1] and A[q + 1 r] such that each element of A[p q - 1] is less than orequal to A[q], which is, in turn, less than or equal to each element of A[q + 1 r].Compute the index q as part of this partitioning procedure.Conquer: Sort the two subarrays A[p q -1] and A[q +1 r] by recursive calls toquicksort.Combine: Since the subarrays are sorted in place, no work is needed to combinethem: the entire array A[p r] is now sorted.The following procedure implements quicksort.QUICKSORT(A, p, r)1 if p < r2then q ← PARTITION(A, p, r)3QUICKSORT(A, p, q - 1)4QUICKSORT(A, q + 1, r)To sort an entire array A, the initial call is QUICKSORT(A, 1, length[A]).Partitioning the arrayThe key to the algorithm is the PARTITION procedure, which rearranges the subarray A[pr] in place.PARTITION(A, p, r)1 x ← A[r]2 i ← p - 13 for j ← p to r - 14do if A[j] ≤ x5then i ← i + 16exchange A[i] ↔ A[j]7 exchange A[i + 1] ↔ A[r]8 return i + 1Figure 7.1 shows the operation of PARTITION on an 8-element array.
PARTITION alwaysselects an element x = A[r] as a pivot element around which to partition the subarray A[p r].As the procedure runs, the array is partitioned into four (possibly empty) regions. At the startof each iteration of the for loop in lines 3-6, each region satisfies certain properties, which wecan state as a loop invariant:Figure 7.1: The operation of PARTITION on a sample array. Lightly shaded array elementsare all in the first partition with values no greater than x. Heavily shaded elements are in thesecond partition with values greater than x. The unshaded elements have not yet been put inone of the first two partitions, and the final white element is the pivot.
(a) The initial array andvariable settings. None of the elements have been placed in either of the first two partitions.(b) The value 2 is "swapped with itself" and put in the partition of smaller values. (c)-(d) Thevalues 8 and 7 are added to the partition of larger values. (e) The values 1 and 8 are swapped,and the smaller partition Grows.
(f) The values 3 and 8 are swapped, and the smaller partitiongrows. (g)-(h) The larger partition grows to include 5 and 6 and the loop terminates. (i) Inlines 7-8, the pivot element is swapped so that it lies between the two partitions.•At the beginning of each iteration of the loop of lines 3-6, for any array index k,1. If p ≤ k ≤ i, then A[k] ≤ x.2. If i + 1 ≤ k ≤ j - 1, then A[k] > x.3. If k = r, then A[k] = x.Figure 7.2 summarizes this structure. The indices between j and r - 1 are not covered by anyof the three cases, and the values in these entries have no particular relationship to the pivot x.Figure 7.2: The four regions maintained by the procedure PARTITION on a subarray A[pr]. The values in A[p i] are all less than or equal to x, the values in A[i + 1 j - 1] are allgreater than x, and A[r] = x.
The values in A[j r - 1] can take on any values.We need to show that this loop invariant is true prior to the first iteration, that each iteration ofthe loop maintains the invariant, and that the invariant provides a useful property to showcorrectness when the loop terminates.••Initialization: Prior to the first iteration of the loop, i = p - 1, and j = p.
There are novalues between p and i, and no values between i + 1 and j - 1, so the first twoconditions of the loop invariant are trivially satisfied. The assignment in line 1satisfies the third condition.Maintenance: As Figure 7.3 shows, there are two cases to consider, depending on theoutcome of the test in line 4. Figure 7.3(a) shows what happens when A[j] > x; theonly action in the loop is to increment j. After j is incremented, condition 2 holds forA[j - 1] and all other entries remain unchanged. Figure 7.3(b) shows what happenswhen A[j] ≤ x; i is incremented, A[i] and A[j] are swapped, and then j is incremented.Because of the swap, we now have that A[i] ≤ x, and condition 1 is satisfied.
Similarly,we also have that A[j - 1] > x, since the item that was swapped into A[j - 1] is, by theloop invariant, greater than x.Figure 7.3: The two cases for one iteration of procedure PARTITION. (a) If A[j] > x,the only action is to increment j, which maintains the loop invariant. (b) If A[j] ≤ x,index i is incremented, A[i] and A[j] are swapped, and then j is incremented.
Again,the loop invariant is maintained.•Termination: At termination, j = r. Therefore, every entry in the array is in one of thethree sets described by the invariant, and we have partitioned the values in the arrayinto three sets: those less than or equal to x, those greater than x, and a singleton setcontaining x.The final two lines of PARTITION move the pivot element into its place in the middle of thearray by swapping it with the leftmost element that is greater than x.The output of PARTITION now satisfies the specifications given for the divide step.The running time of PARTITION on the subarray A[pExercise 7.1-3).r] is Θ(n), where n = r - p + 1 (seeExercises 7.1-1Using Figure 7.1 as a model, illustrate the operation of PARTITION on the array A =19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21 .13,Exercises 7.1-2What value of q does PARTITION return when all elements in the array A[p r] have thesame value? Modify PARTITION so that q = (p+r)/2 when all elements in the array A[p r]have the same value.Exercises 7.1-3Give a brief argument that the running time of PARTITION on a subarray of size n is Θ(n).Exercises 7.1-4How would you modify QUICKSORT to sort into nonincreasing order?7.2 Performance of quicksortThe running time of quicksort depends on whether the partitioning is balanced or unbalanced,and this in turn depends on which elements are used for partitioning.
If the partitioning isbalanced, the algorithm runs asymptotically as fast as merge sort. If the partitioning isunbalanced, however, it can run asymptotically as slowly as insertion sort. In this section, weshall informally investigate how quicksort performs under the assumptions of balanced versusunbalanced partitioning.Worst-case partitioningThe worst-case behavior for quicksort occurs when the partitioning routine produces onesubproblem with n - 1 elements and one with 0 elements.
(This claim is proved in Section7.4.1.) Let us assume that this unbalanced partitioning arises in each recursive call. Thepartitioning costs Θ(n) time. Since the recursive call on an array of size 0 just returns, T(0) =Θ(1), and the recurrence for the running time isT(n) = T(n - 1) + T(0) + Θ(n)= T(n - 1) + Θ(n).Intuitively, if we sum the costs incurred at each level of the recursion, we get an arithmeticseries (equation (A.2)), which evaluates to Θ(n2). Indeed, it is straightforward to use thesubstitution method to prove that the recurrence T(n) = T(n - 1) + Θ(n) has the solution T(n) =Θ(n2). (See Exercise 7.2-1.)Thus, if the partitioning is maximally unbalanced at every recursive level of the algorithm, therunning time is Θ(n2).
Therefore the worst-case running time of quicksort is no better thanthat of insertion sort. Moreover, the Θ(n2) running time occurs when the input array is alreadycompletely sorted-a common situation in which insertion sort runs in O(n) time.Best-case partitioningIn the most even possible split, PARTITION produces two subproblems, each of size no morethan n/2, since one is of size ⌊n/2⌋ and one of size ⌈n/2⌉- 1. In this case, quicksort runs muchfaster. The recurrence for the running time is thenT (n) ≤ 2T (n/2) + Θ(n) ,which by case 2 of the master theorem (Theorem 4.1) has the solution T (n) = O(n lg n).
Thus,the equal balancing of the two sides of the partition at every level of the recursion produces anasymptotically faster algorithm.Balanced partitioningThe average-case running time of quicksort is much closer to the best case than to the worstcase, as the analyses in Section 7.4 will show. The key to understanding why is to understandhow the balance of the partitioning is reflected in the recurrence that describes the runningtime.Suppose, for example, that the partitioning algorithm always produces a 9-to-1 proportionalsplit, which at first blush seems quite unbalanced.
We then obtain the recurrenceT(n) ≤ T (9n/10) + T (n/10) + cnon the running time of quicksort, where we have explicitly included the constant c hidden inthe Θ(n) term. Figure 7.4 shows the recursion tree for this recurrence. Notice that every levelof the tree has cost cn, until a boundary condition is reached at depth log10n = Θ(lgn), andthen the levels have cost at most cn. The recursion terminates at depth log10/9n = Θ(lg n). Thetotal cost of quicksort is therefore O(n lg n).
Thus, with a 9-to-1 proportional split at everylevel of recursion, which intuitively seems quite unbalanced, quicksort runs in O(n lg n) timeasymptotically the same as if the split were right down the middle. In fact, even a 99-to-1 splityields an O(n lg n) running time. The reason is that any split of constant proportionality yieldsa recursion tree of depth Θ(lg n), where the cost at each level is O(n). The running time istherefore O(n lg n) whenever the split has constant proportionality.Figure 7.4: A recursion tree for QUICKSORT in which PARTITION always produces a 9-to1 split, yielding a running time of O(n lg n). Nodes show subproblem sizes, with per-levelcosts on the right.
The per-level costs include the constant c implicit in the Θ(n) term.Intuition for the average caseTo develop a clear notion of the average case for quicksort, we must make an assumptionabout how frequently we expect to encounter the various inputs. The behavior of quicksort isdetermined by the relative ordering of the values in the array elements given as the input, andnot by the particular values in the array. As in our probabilistic analysis of the hiring problemin Section 5.2, we will assume for now that all permutations of the input numbers are equallylikely.When we run quicksort on a random input array, it is unlikely that the partitioning alwayshappens in the same way at every level, as our informal analysis has assumed. We expect thatsome of the splits will be reasonably well balanced and that some will be fairly unbalanced.For example, Exercise 7.2-6 asks you to show that about 80 percent of the time PARTITIONproduces a split that is more balanced than 9 to 1, and about 20 percent of the time it producesa split that is less balanced than 9 to 1.In the average case, PARTITION produces a mix of "good" and "bad" splits.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
