CS6363 Design and Analysis of Computer Algorithms Prof Sergey Bereg Medians and Order Statistics 1 Minimum and Maximum M INIMUM A 1 min A 1 2 for i 2 to length A 3 if min A i then 4 min A i 5 return min The number of comparisons line 3 is n 1 Simultaneous min and max 2n 3 comparisons 3bn 2c The second smallest element How many comparisons are needed 2 Quick Selection The ith order statistics of a set of n elements is the ith smallest element A median is defined for i n 1 2 if n is odd and i n 2 1 lower median or i n 2 1 upper median if n is even The selection problem Given a set A of n distinct numbers and a number i with 1 i n find the element x A that is larger than exactly i 1 elements of A Can be solved by sorting in O n lg n time We show 1 practical algorithm with O n expected running time and 2 theoretical algorithm with O n running time in the worst case R ANDOMIZED S ELECT A p r i 1 if p r then 2 return A p 3 q R ANDOMIZED PARTITION A p r 4 k q p 1 5 if i k then the pivot value is the answer 6 return A q 7 else 8 if i k then 9 return R ANDOMIZED S ELECT A p q 1 i 10 else return R ANDOMIZED S ELECT A q 1 r i k R ANDOMIZED PARTITION A p r Chapter 7 page 154 1 i R ANDOM p r 2 exchange A r A i 3 return PARTITION A p r 1 PARTITION A p r Chapter 7 page 146 1 x A r 2 i p 1 3 for j p to r 1 4 if A j x then 5 i i 1 6 exchange A i A j 7 exchange A i 1 A r 8 return i 1 3 Analysis Let Xk be a random variable that is 1 if A p q contains exactly k elements and Xk 0 otherwise Expected value of Xk is 1 E Xk n If Xk 1 then R ANDOMIZED S ELECT recurses either on A p q 1 or A q 1 r Let T n be the running time Then T n O n n X Xk T max k 1 n k k 1 E T n E O n n X Xk T max k 1 n k k 1 O n O n O n n X k 1 n X k 1 n X k 1 E Xk T max k 1 n k by linearity of expectation E Xk E T max k 1 n k 1 E T max k 1 n k n dn 2e 2 X O n E T n k n k 1 dn 2e 2 X Suppose that E T n an E T n k n k 1 2 We prove E T n cn by induction Step of induction E T n an dn 2e dn 2e 2 X 2 X E T n k an c n k n n k 1 k 1 dn 2e an 2cdn 2e 2c X k n k 1 2c dn 2e dn 2e 1 n 2 2c n2 n2 1 c n an cn 2c an cn 2c 1 n 2 2 2 c 5c cn n a 4 2 c 5c cn if n a 4 2 an 2c n 2 1 It holds if c 4 a c 8 or c 8a and n 20 4 Deterministic Algorithm S ELECTION A n 1 Divide n elements into dn 5e groups of at most 5 elements each 2 Find median in each group by sorting it 3 Find median of medians x recursively call S ELECTION for an array of medians 4 Partition the input array A using pivot x Let x be kth element of A 5 If i k then return x Otherwise recursively find ith element on the low side if i k or i k th element on the high side if i k 5 Example Given an array A with 53 numbers A 33 22 30 14 45 10 44 23 9 39 38 52 6 5 50 37 11 26 3 15 2 53 40 54 25 55 12 19 31 16 18 13 1 48 41 24 43 46 47 17 34 20 31 32 33 35 4 49 51 7 21 27 8 Compute 10th smallest number Step 1 Divide n elements into dn 5e groups 33 22 30 14 45 10 44 23 9 39 38 52 6 5 50 37 11 26 3 15 2 53 40 54 25 55 12 19 31 16 18 13 1 48 41 24 43 46 47 17 34 20 31 32 33 35 4 49 51 7 3 21 27 8 2 Find the median in each group by sorting it 14 22 30 33 45 9 10 23 39 44 5 6 38 50 52 3 11 15 26 37 2 25 40 53 54 12 16 19 31 53 1 13 18 41 48 17 24 43 46 47 20 31 32 33 34 4 7 35 49 51 8 21 27 3 Find median of medians recursively i e find 6th smallest number in the array 30 23 38 15 40 19 18 43 32 35 21 x 30 14 9 5 3 2 12 1 17 20 4 22 10 6 11 25 16 13 24 31 7 8 30 23 38 15 40 19 18 43 32 35 21 33 39 50 26 53 31 41 46 33 49 27 45 44 52 37 54 53 48 47 34 51 4 Partition the array A using pivot x Let x be kth element of A Low 22 14 10 23 9 6 5 11 26 3 15 2 25 12 19 16 18 13 1 24 17 20 4 7 21 27 8 High 33 45 44 39 38 52 50 37 53 40 54 55 31 48 41 43 46 47 34 31 32 33 35 49 51 k 28 5 Recursively find 10th element in Low 6 Running Time Let T n be the running time for computing the kth smallest element of n numbers Step 1 and 2 O n time Step 3 T d n5 e time Step 4 O n time Step 5 T max L H time where L is the low side and H is the high side We will show later that L H 7n 10 6 Recurrence T n T d n5 e T 7n 10 6 an Simplified recurrence T n T n 5 T 7n 10 an We pick the constant c 10a and show by induction that T n cn T n T n 5 T 7n 10 an cn 5 c 7n 10 an 9cn 10 an cn cn 10 an cn We show that L 3 d …
View Full Document
Unlocking...