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?
Naïve = 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)
18
Select
Select 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, done
19
Select
Does this work for making: (1) n/3 groups of 3?
(2) n/7 groups of 7?
(3) n/9 groups of 9?
20
Select