# 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?

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