UF COP 3530 - Rank (11 pages)

Previewing pages 1, 2, 3, 4 of 11 page document View the full content.
View Full Document

Rank



Previewing pages 1, 2, 3, 4 of actual document.

View the full content.
View Full Document
View Full Document

Rank

56 views


Pages:
11
School:
University of Florida-Gainesville
Course:
Cop 3530 - Data Structures and Algorithms

Unformatted text preview:

Rank Rank of an element is its position in ascending key order 2 6 7 8 10 15 18 20 25 30 35 40 rank 2 0 rank 15 5 rank 20 7 Selection Problem Given n unsorted elements determine the k th smallest element That is determine the element whose rank is k 1 Applications Median score on a test k ceil n 2 Median salary of Computer Scientists Identify people whose salary is in the bottom 10 First find salary at the 10 rank Selection By Sorting Sort the n elements Pick up the element with desired rank O n log n time Divide And Conquer Selection Small instance has n 1 Selection is easy When n 1 select a pivot element from out of the n elements Partition the n elements into 3 groups left middle and right as is done in quick sort The rank of the pivot is the location of the pivot following the partitioning If k 1 rank pivot pivot is the desired element If k 1 rank pivot determine the k th smallest element in left If k 1 rank pivot determine the k rank pivot 1 th smallest element in right D C Selection Example Find kth element of a 3 2 8 0 11 10 1 2 9 7 1 Use 3 as the pivot and partition a 1 2 1 0 2 34 10 11 9 7 8 rank pivot 5 So pivot is the 6 th smallest element D C Selection Example a 1 2 1 0 2 34 10 11 9 7 8 If k 6 k 1 rank pivot pivot is the element we seek If k 6 k 1 rank pivot find k th smallest element in left partition If k 6 k 1 rank pivot find krank pivot 1 th smallest element in right partition Time Complexity Worst case arises when the partition to be searched always has all but the pivot O n2 Expected performance is O n Worst case becomes O n when the pivot is chosen carefully Partition into n 9 groups with 9 elements each last group may have a few more Find the median element in each group pivot is the median of the group medians This median is found using select recursively Closest Pair Of Points Given n points in 2D find the pair that are closest Applications We plan to drill holes in a metal sheet If the holes are too close the sheet will tear during drilling



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Rank and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Rank and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?