Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 30
Текст из файла (страница 30)
Todo so, we must understand when the algorithm compares two elements of the array and whenit does not. For ease of analysis, we rename the elements of the array A as z1, z2,..., zn, with zibeing the ith smallest element. We also define the set Zij = {zi, zi+1,..., zj} to be the set ofelements between zi and zj, inclusive.When does the algorithm compare zi and zj? To answer this question, we first observe thateach pair of elements is compared at most once.
Why? Elements are compared only to thepivot element and, after a particular call of PARTITION finishes, the pivot element used inthat call is never again compared to any other elements.Our analysis uses indicator random variables (see Section 5.2). We defineXij = I {zi is compared to zj} ,where we are considering whether the comparison takes place at any time during theexecution of the algorithm, not just during one iteration or one call of PARTITION. Sinceeach pair is compared at most once, we can easily characterize the total number ofcomparisons performed by the algorithm:Taking expectations of both sides, and then using linearity of expectation and Lemma 5.1, weobtain(7.2)It remains to compute Pr {zi is compared to zj}.It is useful to think about when two items are not compared.
Consider an input to quicksort ofthe numbers 1 through 10 (in any order), and assume that the first pivot element is 7. Then thefirst call to PARTITION separates the numbers into two sets: {1, 2, 3, 4, 5, 6} and {8, 9, 10}.In doing so, the pivot element 7 is compared to all other elements, but no number from thefirst set (e.g., 2) is or ever will be compared to any number from the second set (e.g., 9).In general, once a pivot x is chosen with zi < x < zj, we know that zi and zj cannot be comparedat any subsequent time. If, on the other hand, zi is chosen as a pivot before any other item inZij, then zi will be compared to each item in Zij, except for itself.
Similarly, if zj is chosen as apivot before any other item in Zij, then zj will be compared to each item in Zij , except foritself. In our example, the values 7 and 9 are compared because 7 is the first item from Z7,9 tobe chosen as a pivot. In contrast, 2 and 9 will never be compared because the first pivotelement chosen from Z2,9 is 7. Thus, zi and zj are compared if and only if the first element tobe chosen as a pivot from Zij is either zi or zj.We now compute the probability that this event occurs. Prior to the point at which an elementfrom Zij has been chosen as a pivot, the whole set Zij is together in the same partition.Therefore, any element of Zij is equally likely to be the first one chosen as a pivot. Becausethe set Zij has j - i + 1 elements, the probability that any given element is the first one chosenas a pivot is 1/(j - i + 1).
Thus, we have(7.3)The second line follows because the two events are mutually exclusive. Combining equations(7.2) and (7.3), we get thatWe can evaluate this sum using a change of variables (k = j - i) and the bound on theharmonic series in equation (A.7):(7.4)Thus we conclude that, using RANDOMIZED-PARTITION, the expected running time ofquicksort is O(n lg n).Exercises 7.4-1Show that in the recurrenceExercises 7.4-2Show that quicksort's best-case running time is Ω(n lg n).Exercises 7.4-3Show that q2 + (n - q - 1)2 achieves a maximum over q = 0, 1,..., n - 1 when q = 0 or q = n - 1.Exercises 7.4-4Show that RANDOMIZED-QUICKSORT's expected running time is Ω(n lg n).Exercises 7.4-5The running time of quicksort can be improved in practice by taking advantage of the fastrunning time of insertion sort when its input is "nearly" sorted.
When quicksort is called on asubarray with fewer than k elements, let it simply return without sorting the subarray. Afterthe top-level call to quicksort returns, run insertion sort on the entire array to finish the sortingprocess. Argue that this sorting algorithm runs in O(nk + n lg(n/k)) expected time. Howshould k be picked, both in theory and in practice?Exercises 7.4-6: ⋆Consider modifying the PARTITION procedure by randomly picking three elements fromarray A and partitioning about their median (the middle value of the three elements).Approximate the probability of getting at worst an αto-(1 - α) split, as a function of α in therange 0 < α < 1.Problems 7-1: Hoare partition correctnessThe version of PARTITION given in this chapter is not the original partitioning algorithm.Here is the original partition algorithm, which is due to T. Hoare:HOARE-PARTITION(A, p, r)1 x ← A[p]2 i ← p - 13 j ← r + 14 while TRUE5do repeat j ← j - 16until A[j] ≤ x7repeat i ← i + 18until A[i] ≥ x9if i < j10then exchange A[i] ↔ A[j]11else return ja.
Demonstrate the operation of HOARE-PARTITION on the array A = 13, 19, 9, 5,12, 8, 7, 4, 11, 2, 6, 21 , showing the values of the array and auxiliary values aftereach iteration of the for loop in lines 4-11.The next three questions ask you to give a careful argument that the procedure HOAREPARTITION is correct.
Prove the following:b. The indices i and j are such that we never access an element of A outside the subarrayA[p r].c. When HOARE-PARTITION terminates, it returns a value j such that p ≤ j < r.d. Every element of A[p j] is less than or equal to every element of A[j +1 r] whenHOARE-PARTITION terminates.The PARTITION procedure in Section 7.1 separates the pivot value (originally in A[r]) fromthe two partitions it forms. The HOARE-PARTITION procedure, on the other hand, alwaysplaces the pivot value (originally in A[p]) into one of the two partitions A[p j] and A[j + 1r]. Since p ≤ j < r, this split is always nontrivial.e. Rewrite the QUICKSORT procedure to use HOARE-PARTITION.Problems 7-2: Alternative quicksort analysisAn alternative analysis of the running time of randomized quicksort focuses on the expectedrunning time of each individual recursive call to QUICKSORT, rather than on the number ofcomparisons performed.a.
Argue that, given an array of size n, the probability that any particular element ischosen as the pivot is 1/n. Use this to define indicator random variables Xi = I{ithsmallest element is chosen as the pivot}. What is E [Xi]?b. Let T (n) be a random variable denoting the running time of quicksort on an array ofsize n. Argue that(7.5)c.
Show that equation (7.5) simplifies to(7.6)d. Show that(7.7)e. (Hint: Split the summation into two parts, one for k = 1, 2,..., ⌈n/2⌉ - 1 and one for k =⌈n/2⌉,..., n - 1.)f. Using the bound from equation (7.7), show that the recurrence in equation (7.6) hasthe solution E [T (n)] = Θ(n lg n). (Hint: Show, by substitution, that E[T (n)] ≤ an logn - bn for some positive constants a and b.)Problems 7-3: Stooge sortProfessors Howard, Fine, and Howard have proposed the following "elegant" sortingalgorithm:STOOGE-SORT(A, i, j)1 if A[i] > A[j]2then exchange A[i] ↔ A[j]3 if i + 1 ≥ j4then return5k ← ⌊(j - i + 1)/3⌋6STOOGE-SORT(A, i, j - k)7STOOGE-SORT(A, i + k, j)8STOOGE-SORT(A, i, j - k)▹ Round down.▹ First two-thirds.▹ Last two-thirds.▹ First two-thirds again.a.
Argue that, if n = length[A], then STOOGE-SORT(A, 1, length[A]) correctly sorts theinput array A[1 n].b. Give a recurrence for the worst-case running time of STOOGE-SORT and a tightasymptotic (Θ-notation) bound on the worst-case running time.c. Compare the worst-case running time of STOOGE-SORT with that of insertion sort,merge sort, heapsort, and quicksort. Do the professors deserve tenure?Problems 7-4: Stack depth for quicksortThe QUICKSORT algorithm of Section 7.1 contains two recursive calls to itself.
After thecall to PARTITION, the left subarray is recursively sorted and then the right subarray isrecursively sorted. The second recursive call in QUICKSORT is not really necessary; it canbe avoided by using an iterative control structure. This technique, called tail recursion, isprovided automatically by good compilers. Consider the following version of quicksort,which simulates tail recursion.QUICKSORT'(A, p, r)1 while p < r2345do ▸ Partition and sort left subarray.q ← PARTITION(A, p, r)QUICKSORT'(A, p, q - 1)p ← q + 1a. Argue that QUICKSORT'(A, 1, length[A]) correctly sorts the array A.Compilers usually execute recursive procedures by using a stack that contains pertinentinformation, including the parameter values, for each recursive call.
The information for themost recent call is at the top of the stack, and the information for the initial call is at thebottom. When a procedure is invoked, its information is pushed onto the stack; when itterminates, its information is popped. Since we assume that array parameters are representedby pointers, the information for each procedure call on the stack requires O(1) stack space.The stack depth is the maximum amount of stack space used at any time during acomputation.b.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
