CSE310 Lecture 12 Selection in Linear Time Guoliang Larry Xue Department of CSE Arizona State University http optimization asu edu xue Guoliang Xue asu edu Topics of this lecture Finding the Smallest Selection in Linear Time break into groups of 5 select median of the medians partition using the median of medians recursive call if necessary Applications of Medians Quicksort in optimal worst case time Finding the kth smallest element 2 Guoliang Xue asu edu Finding the smallest How can we find the smallest of n elements Make n 1 comparisons Can we do with fewer comparisons No we need n 1 comparisons to identify the smallest element 3 Guoliang Xue asu edu Finding the smallest Smallest A n xv A 1 xi 1 for i 2 i n i if A i xv then xv A i xi i return xi 4 Guoliang Xue asu edu Finding the k th smallest Given an unsorted array A of n elements and an integer k find the k th smallest element in A int select A p r k 5 Guoliang Xue asu edu Worst Case Linear Time Selection That is the algorithm that we present for the k selection problem runs in time O n This algorithm is not very intuitive Idea recursively partition the array into subarrays then solve problems recursively find a good split of the array the algorithm uses a modified version of the quicksort PARTITION procedure where we take the pivot element around which we do the partition as a parameter 6 Guoliang Xue asu edu sort medians of groups sort groups group with fixed constant number of elements each 7 x elements x Guoliang Xue asu edu Algorithm SELECT A k for finding the kth smallest element of an input array A with n elements Step1 Divide the n elements of A into n 5 groups of 5 elements each and at most one group made up of the remaining n mod 5 elements Step2 Find the median of each of the n 5 groups by insertion sorting the at most 5 elements of each group and taking its middle element if the group has an even of elements take the larger of the two medians Step3 Use SELECT recursively to find the median x of the n 5 medians found in Step2 Step4 Partition A around the median of the medians x using a modified version of quicksort s PARTITION that takes x as a parameter and uses x as the pivot element Let i be the number of elements on the low side of the partition n i elements on high side Step5 Use SELECT recursively to find the kth smallest element on the low side if k i or k i th smallest element onGuoliang Xue asu edu the high side 8 Step5 We call SELECT A 1 i k if k i or SELECT A i 1 n k i if k i x medians of each group x is the median ofthe medians elements x a b n 5 groups 9 steps 2 3 Guoliang Xue asu edu we know a b from or 4 of SELECT A k for simplicity assume all n elements in h are distinct at least half of the medians found in Step2 are x at least half of the n 5 groups but for the one group that may contain 5 elements and the group that contains x itself contribute with 3 elements that are x the number of elements that are x is at least 3 n 5 2 3n 10 6 2 Similarly the number of elements that are x is at least 3n 10 6 Thus in the worst case SELECT is called recursively on at most 7n 10 6 elements in Step5 10 Guoliang Xue asu edu Worst Case Running Time of SELECT A k Steps 1 2 and 4 O n time Step2 consists of O n calls of insertion sort on sets with 5 elements each T n worst case running time of SELECT on an array with n elements Step3 T n 5 time Step 5 T 7n 10 6 time follows from previous considerations Thus T n 1 if n n0 constants 0 T n 5 T 7n 10 6 bn if n n0 e g n0 1 or n0 5 and b 1 11 Guoliang Xue asu edu This recurrence relation solves to T n cn O n constant 0 For n0 and c large enough e g for n0 80 and c b In order to check that this is a valid upper bound on T n simply substitute T x by c x on the right hand side of the recurrence relations on previous slide and assume n0 80 and c b 12 Guoliang Xue asu edu Applications Quicksort in O n log n worst case time Finding the kth smallest in linear time Many other applications 13 Guoliang Xue asu edu Summary Median of Medians for Finding the Median Applications of the median k smallest element quicksort in optimal time What happens if we change 5 to 7 What happens if we change 5 to 3 14 Guoliang Xue asu edu Readings The materials covered in this lecture can be found in Section 9 3 Work on Exercises 9 3 1 9 3 2 9 3 3 9 3 5 and Problem 9 2 15 Guoliang Xue asu edu
View Full Document
Unlocking...