# UF COP 3530 - Rank (11 pages)

Previewing pages*1, 2, 3, 4*of 11 page document

**View the full content.**# Rank

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

**View the full content.**View Full Document

## Rank

0 0 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