# UF COP 3530 - Rank (11 pages)

Previewing pages 1, 2, 3, 4 of 11 page document
View Full Document

# Rank

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

View Full Document
View Full Document

## Rank

56 views

Pages:
11
School:
University of Florida-Gainesville
Course:
Cop 3530 - Data Structures and Algorithms
##### Data Structures and Algorithms Documents
• 16 pages

• 10 pages

• 4 pages

• 24 pages

• 20 pages

• 10 pages

• 10 pages

• 24 pages

• 33 pages

• 24 pages

• 62 pages

• 29 pages

• 2 pages

• 2 pages

• 21 pages

• 13 pages

• 8 pages

• 27 pages

• 23 pages

• 11 pages

• 11 pages

• 5 pages

• 24 pages

• 20 pages

• 33 pages

• 24 pages

• 43 pages

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

Unlocking...