c Balaji Raghavachari 38 Algorithm Design and Analysis c Balaji Raghavachari 39 Algorithm Design and Analysis In place O n Randomized Partition algorithm DAC Example Quick sort Input Array A p r with pivot element A r x If n is small use Insertion sort Otherwise select a pivot element x from A p r uniformly at random Output Rearrange A p r and return q such that A p q 1 x Partition A p r into A p q and A q 1 r A i A i x A i A i x x q 1 q p r Sort the subarrays recursively There is an e cient in place partition algorithm Expected running time is O n log n c Balaji Raghavachari 40 Algorithm Design and Analysis A q x i Random p r Exchange A i and A r x A r i p 1 for j p to r 1 do if A j x then i i 1 Exchange A i and A j Exchange A i 1 and A r return i 1 c Balaji Raghavachari 41 A q 1 r x Loop invariant At the beginning of each iteration of the loop A p i x A i 1 j 1 x A j r 1 is unprocessed A r x Algorithm Design and Analysis Illustration of Partition Quick sort algorithm Before the loop 2 1 4 p i 9 7 i 1 j 1 3 8 6 j 0 5 r 1 r 0 5 r 1 r Algorithm QuickSort A p r Sort A p r if p r then q Randomized P artition A p r QuickSort A p q 1 QuickSort A q 1 r Here A j x A i 1 and A j are exchanged 2 1 4 3 p 7 i 9 i 1 8 j 6 j 1 At the end of the loop j is incremented and the L I is valid for the next iteration In the next iteration A j x Running time of Quick sort is a random variable Its expected value is O n log n After the loop Read correctness of Partition from book Try to write correctness of Quick sort by yourself 2 p 1 4 3 7 i i 1 9 8 j 6 0 5 j 1 r 1 r c Balaji Raghavachari 42 Algorithm Design and Analysis c Balaji Raghavachari 43 Algorithm Design and Analysis Running time analysis of Quick sort By de nition E Xij P r zi is compared to zj The running time of Quick sort is O n X where X is the number of comparisons made by partition Suppose at some point a pivot x is chosen such that zi x zj Then after this step zi and zj will be in di erent subarrays that are sorted separately and therefore will never be compared to each other From the code if two elements are compared to each other then one of them is the current pivot Suppose the elements after sorting are z1 z2 zn i e zi is the element with rank i Let Zij zi zi 1 zj Therefore zi will be compared to zj only if one of zi or zj is chosen as pivot rst in Zij De ne Xij I zi is compared to zj an indicator random variable that is 1 i zi and zj are compared X n 1 n P r zi is compared to zj P r zi is chosen as pivot in Zij rst P r zj is chosen as pivot in Zij rst 1 1 j i 1 j i 1 Xij i 1 j i 1 E X E n 1 n Xij 44 n E Xij i 1 j i 1 i 1 j i 1 c Balaji Raghavachari n 1 Algorithm Design and Analysis 2 j i 1 c Balaji Raghavachari 11 Algorithm Design and Analysis Approximation by integrals E X n 1 n E Xij i 1 j i 1 n 1 For a monotonically increasing function f k n n 1 n f x dx f k f x dx n 2 j i 1 i 1 j i 1 m 1 n i n 1 See page 1068 for proof of inequality 2 substituting k j i k 1 i 1 k 1 n 1 1 1 1 2 2 3 n i 1 i 1 2c n 1 For monotonically decreasing functions replace by Example n x ln xdx 1 log n i 1 m k m k 2 n 1 k ln k x ln xdx 2 2 x2 x x2 x2 x2 ln x d ln x ln x x ln xdx ln xd 2 2 2 2 4 n Combining the equations k 2 k ln k n2 ln n 2cn log n O n log n n
View Full Document
Unlocking...