[SOLVED] CS Selection

Selection
1

Selection given a set of (distinct) elements, finding the element larger than i 1 other elements
Selection with
i=n is finding maximum i=1 is finding minimum i=n/2 is finding median
2
Selection

Selection for any i is O(n) runtime Find max in O(n)?
3
Maximum

Selection for any i is O(n) runtime Find max in O(n)?
max = A[ 1 ]
for i = 2 to A.length
if ( A[ i ] > max ) max = A[ i ]
4
Maximum

It takes about n comparisons to find max
How many would it take to find both max and min at same time?
5
Max and min

It takes about n comparisons to find max
How many would it take to find both max and min at same time?
Naive = 2n Smarter = 3/2 n
6
Max and min

smin = min(A[ 1 ], A[ 2 ]) smax = max(A[ 1 ], A[ 2 ]) for i = 3 to A.length step 2
if (A[ i ] > A[ i+1 ])
smax = max(A[ i ], smax) smin = min(A[ i+1], smin)
else
smax = max(A[ i+1], smax) smin = min(A[ i ], smin)
7
Max and min

Remember quicksort?
Partition step
8
Randomized selection

To select i:
1. Partition on random element
2. If partitioned element i, end otherwise recursively partition on side with i
9
Randomized selection

{2, 6, 4, 7, 8, 4, 7, 2} find i = 5
10
Randomized selection

{2, 6, 4, 7, 8, 4, 7, 2} find i = 5 Pick pivot = 4
{2, 6, 4, 7, 8, 2, 7, 4}
{2, 6, 4, 7, 8, 2, 7, 4}
{2, 6, 4, 7, 8, 2, 7, 4} {2, 4, 6, 7, 8, 2, 7, 4} {2, 4, 6, 7, 8, 2, 7, 4} {2, 4, 6, 7, 8, 2, 7, 4}
11
Randomized selection

{2, 4, 6, 7, 8, 2, 7, 4} {2, 4, 2, 7, 8, 6, 7, 4} {2, 4, 2, 7, 8, 6, 7, 4} {2, 4, 2, 4, 8, 6, 7, 7}
1, 2, 3, 4, 5, 6, 7, 8
i=5 on green side, recurse
12
Randomized selection

{8, 6, 7, 7} pick pivot = 6 {8, 7, 7, 6}
{8, 7, 7, 6}
{8, 7, 7, 6}
{8, 7, 7, 6} {6, 7, 7, 8}
5, 6, 7, 8
found i=5, value = 6
13
Randomized selection

Quicksort runs in O(n lg n), but we only have sort one side and sometimes stop early
This gives randomized selection O(n) running time
(proof in book, I punt)
14
Randomized selection

Just like quicksort, the worst case running time is O(n2)
This happens when you want to find the min, but always partition on the max
15
Randomized selection

A worst case O(n) selection is given by Select: (see code)
1. Make n/5 groups of 5 and find
their medians (via sorting)
2. Recursively find the median of
the n/5 medians (using Select) 3. Partition on median of medians 4. Recursively Select correct side
16
Select

Proof of the general case: // assume T(n) is O(n)
If T(n) is O(n) then
17
Select

// Pick n > 2(sumi qi/(1 sumi ki))
Done if sumi ki < 1 (just need show for this n multiples) 18SelectSelect runs in:T(n) = T(ceiling(n/5))+T(7n/10 + 6) + O(n)By the previous proof this is O(n): ceiling(n/5) + 7n/10 + 6< n/5 + 1 + 7n/10 + 6 = 9n/10 + 7 sumi ki = 9/10 < 1, done19SelectDoes this work for making: (1) n/3 groups of 3?(2) n/7 groups of 7?(3) n/9 groups of 9? 20Select