CSE310 Lecture 12: Selection in Linear TimeTopics of this lectureFinding the smallest…Finding the smallestFinding the k-th smallest…PowerPoint PresentationSlide 7Slide 8Slide 9Slide 10Slide 11Slide [email protected] Lecture 12:CSE310 Lecture 12:Selection in Linear TimeSelection in Linear TimeGuoliang (Larry) XueDepartment of CSEArizona State Universityhttp://optimization.asu.edu/[email protected] of this lectureTopics of this lectureFinding the SmallestSelection in Linear Timebreak into groups of 5select median of the medianspartition using the median of mediansrecursive call if necessaryApplications of MediansQuicksort in optimal worst-case timeFinding the kth smallest [email protected] the smallest…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 [email protected] the smallestFinding the smallestSmallest(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;[email protected] the k-th smallest…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)[email protected]= 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 [email protected] medians of groupssort groups…group with fixed (constant) number of elements each.elements > [email protected] 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 on the high [email protected]…x (Step5:) We callSELECT(A[1 .. i], k), if k < i or SELECT(A[i+1 .. n], k-i), if k > i.>>>>medians of each group. (x is the median-of-the-medians)elements > x= we know a > b (from steps 2, 3, or 4 of SELECT(A, k) ).n/5 [email protected]• 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 least3 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 [email protected]= 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)• ThusT(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)[email protected]• This recurrence relation solves toT(n) < cn = O(n)constant > 0For 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 = [email protected]Quicksort in O(n log n) worst-case time.Finding the kth smallest in linear time.Many other [email protected]Median of Medians for Finding the MedianApplications of the mediank-smallest elementquicksort in optimal timeWhat happens if we change 5 to 7?What happens if we change 5 to [email protected]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
View Full Document
Unlocking...