c� Balaji Raghavachari 38 Algorithm Design and Analysis✬✫✩✪DAC Example: Quick sort• If n is small, use Insertion sort. Otherwise, sele ct apivot element x from A[p . . . r], uniformly at random.• Partition A[p . . . r] into A[p . . . q] and A[q + 1 . . . r]:{A[i] | A[i] > x}pq + 1rx{A[i] | A[i] ≤ x}q• Sort the subarrays recursively.• There is an efficient in-place partition algorithm.• Expected running time is O(n log n).c� Balaji Raghavachari 39 Algorithm Design and Analysis✬✫✩✪In-place O(n) Randomized Partition algorithm• Input: Array A[p..r], with pivot element A[r] = x• Output: Rearrange A[p..r] and return q, such thatA[p..q − 1] ≤ x A[q] = x A[q + 1..r] > xi ← Random(p, r)Exchange A[i] and A[r]x ← A[r]i ← p − 1for j ← p to r − 1 doif A[j] ≤ x theni ← i + 1Exchange A[i] and A[j]Exchange A[i + 1] and A[r]return i + 1Loop invariant: At the begin-ning of each iteration of theloop, A[p..i] ≤ x,A[i + 1..j − 1] > x,A[j..r − 1] is unprocessed,A[r] = x.c� Balaji Raghavachari 40 Algorithm Design and Analysis✬✫✩✪Illustration of PartitionBefore the loop:2 1 4 9 7 3 8 6 0 5p i i + 1 j − 1 j r − 1 rHere A[j] ≤ x. A[i + 1] and A[j] are exchanged:2 1 4 3 7 9 8 6 0 5p i i + 1 j j + 1 r − 1 rAt the end of the loop, j is incremented, and the L.I. isvalid for the next iteration. In the next iteration, A[j] > x.After the loop:2 1 4 3 7 9 8 6 0 5p i i + 1 j j + 1 r − 1 rc� Balaji Raghavachari 41 Algorithm Design and Analysis✬✫✩✪Quick sort algorithmAlgorithm QuickSort(A, p, r): // Sort A[p..r]if p < r thenq ← RandomizedP artition(A, p, r)QuickSort(A, p, q − 1)QuickSort(A, q + 1, r)• Running time of Quick sort is a random variable. Itsexpected value is O(n log n).• Read correctness of Partition from book. Try to writecorrectness of Quick sort by yourself.c� Balaji Raghavachari 42 Algorithm Design and Analysis✬✫✩✪Running time analysis of Quick sort• The running time of Quick sort is O(n + X), where X isthe number of comparisons made by partition• From the code, if two elements are compared to eachother, then one of them is the current pivot• Suppose the elements after sorting are z1, z2, . . . , zn, i.e.,ziis the element with rank i. Let Zij= {zi, zi+1, . . . , zj}• Define Xij= I{ziis compared to zj}, an indicatorrandom variable that is 1 iff ziand zjare comparedX =n−1�i=1n�j=i+1XijE[X] = E�n−1�i=1n�j=i+1Xij�=n−1�i=1n�j=i+1E[Xij]c� Balaji Raghavachari 43 Algorithm Design and Analysis✬✫✩✪• By definition, E[Xij] = P r{ziis compared to zj}• Suppose at some point, a pivot x is chosen such thatzi< x < zj. Then after this step, ziand zjwill be indifferent subarrays that are sorted separately, andtherefore will never be compared to each other• Therefore ziwill be compared to zjonly if one of ziorzjis chosen as pivot first in Zij• P r{ziis compared to zj}= P r{ziis chosen as pivot in Zijfirst}+ P r{zjis chosen as pivot in Zijfirst}=1j−i+1+1j−i+1=2j−i+1c� Balaji Raghavachari 44 Algorithm Design and Analysis✬✫✩✪E[X] =n−1�i=1n�j=i+1E[Xij] =n−1�i=1n�j=i+12j − i + 1=n−1�i=1n−i�k=12k + 1(substituting k = j − i)= 2n−1�i=1�12+13+ . . . +1n − i + 1�≤ 2cn−1�i=1log n≤ 2cn log n = O(n log n)c� Balaji Raghavachari 11 Algorithm Design and Analysis✬✫✩✪Approximation by integralsFor a monotonically increasing function f (k),�nm−1f(x)dx ≤n�k=mf(k) ≤�n+1mf(x)dx.• See page 1068 for proof of inequality.• For monotonically decreasing functions, replace ≤ by ≥.• Example:�n1x ln xdx ≤n�k=2k ln k ≤�n+12x ln xdx.�x ln xdx =�ln xdx22=x22ln x −�x22d ln x =x22ln x −x24.• Combining the equations,�nk=2k ln k = Θ(n2ln
View Full Document
Unlocking...