Deterministic Selection PDF

Preview

Summary

Lecture 12 - Deterministic Selection...

Description

Deterministic*Selection

Questions 1. 2. 3. 4.

What'is'the'purpose'of'the'master'theorem? How'did'we'prove'the'master'theorem? What'was'the'runtime'of'Quicksort? What'are'the'major'benefits'of'Quicksort'(compared'to'other' sorting'algorithms)? 5. How'did'we'compute'the'runtime'of'quicksort? 6. What'is'the'runtime'of'randomized'selection'(Quickselect)? 7. How'did'we'compute'the'runtime'of'randomized'selection?

1

Selection Randomized'selection • Fast'and'practical • All'operations'done'in-place • Small'constant'factors Deterministic'selection'(guaranteed'O(n)'runtime) • Slower'in'practice • Extra'memory'required • Large'constant'factors'(extra'non-recursive'work)

Selection*Problem • Input:'an'array'A'of'length'n'with'a'permutation'of'the'numbers'1..n • Output:'the'ith order'statistic

2

Randomized*Selection*Algorithm QUICKSELECT (A, l, r, i) if l == r return A[l] // move pivot to l p = PARTITION (A, l, r) if i == p then return A[i] if i < p then return QUICKSELECT (A, l, p - 1, i) else return QUICKSELECT (A, p + 1, r, i-p)

Randomized*Selection • Hope:'that'the'choice'of'pivot'is'“good'enough”'“often'enough” • Theorem:'for'every'input'array,'the'average'running'time'of' randomized'selection'is'O(n)

3

Deterministic*Selection Deterministically choose'“good”'pivot'(50-50'split) • Median Goal:'select'a'pivot'that'is'guaranteed to'be'pretty'good Key'idea:'find'the'median'of'medians

Deterministic*Selection*Pivot*Selection • Break'input'array'into'groups,'each'of'size'5'(n/5'total'groups) • Sort'each'group • Copy'the'n/5'medians'(middle'elements)'from'each'group'into'a'new' array'called'C • Recursively'compute'the'median'of'C • Return'this'value'as'the'pivot

4

Deterministic*Selection DSELECT(A, i) if A.n = 1, return A[1] break into groups of size 5 and sort C = medians of the groups of size 5 pivot = DSELECT(C, A.n/5/2)

Base'Case Recursively'find' median'of'medians

left, right, p = PARTITION(A, pivot) if p = i, return pivot else if p < i, return DSELECT(left, i) else if p > i, return DSELECT(right, i-p)

Partition Recursion

Deterministic*Selection DSELECT(A, i) if A.n = 1, return A[1] break into groups of size 5 and sort C = medians of the groups of size 5 pivot = DSELECT(C, A.n/5/2)

What'is'the' running'time? Quiz

left, right, p = PARTITION(A, pivot) if p = i, return pivot else if p < i, return DSELECT(left, i) else if p > i, return DSELECT(right, i-p)

5

DSELECT*Running*Time Theorem:'for'every'input'array'of'length'n,'DSELECT'returns'the'ith order'statistic'in'O(n) Seems'impossible'since'we’ve'added'another'recursive'call'and'a' bunch'of'work'to'find'the'median'of'medians

Deterministic*Selection DSELECT(A, i) if A.n = 1, return A[1] O(1)

O(n)

break into groups of size 5 and sort C = medians of the groups of size 5 T(n/5) pivot = DSELECT(C, n/5/2)

O(n)

left, right, p = PARTITION(A, pivot)

O(n)

O(1)

if p = i, return pivot else if p < i, return DSELECT(left, i) else if p > i, return DSELECT(right, i-p)

T(?)

6

Sorting*5*elements A

B

C

D

E

19

11

17

7

13

1

Sorting*5*elements A

B

C

D

E

11

19

17

7

13

1

A

2

B

7

Sorting*5*elements A

B

C

D

E

11

19

7

17

13

1

2 3

A

B

C

D

Sorting*5*elements A

B

C

D

E

7

17

11

19

13

1

2 3

A

4 B

C

D

8

Sorting*5*elements A

B

C

D

E

7

17

11

19

13

1

2 3

4

A

5

B

C

D

E

Sorting*5*elements A

B

C

D

E

7

17

11

19

13

1

2 3

A

4 6

B

C

E

5

D

9

Sorting*5*elements A

B

C

D

E

7

17

11

19

13

1

2 3

4 7

6

A

C

E

B

5

D

At'most'7'comparisons!

DSELECT*Running*Time T(n)'='maximum'#'of'operations'required'for'input'of'length'n 𝑇 1 =1 𝑇 𝑛 ≤ 𝑐𝑛 + 𝑇

𝑛 + 𝑇(? ) 5

Sorting,' partitioning,' copying,'etc.

10

DSELECT*Running*Time T(n)'='maximum'#'of'operations'required'for'input'of'length'n 𝑇 1 =1 𝑇 𝑛 ≤ 𝑐𝑛 + 𝑇

𝑛 + 𝑇(? ) 5

Sorting,' partitioning,' copying,'etc.

On'what'does'this' “?”'depend?

DSELECT*Running*Time T(n)'='maximum'#'of'operations'required'for'input'of'length'n 𝑇 1 =1 𝑇 𝑛 ≤ 𝑐𝑛 + 𝑇 Sorting,' partitioning,' copying,'etc.

𝑛 + 𝑇(? ) 5

Lemma:' the'second'recursive'call' is'guaranteed'to'be'on'an' array'of'size'='1'for'T(n)'='O(n) Proof'by'induction Base'Case:'T(1)'='1'='1) Inductive'Hypothesis:'Assume'we’ve'proved'the'bound'for'T(k)'for'k'...