Linear-‐Time
Selec.on
Randomized
Selec.on
(Algorithm)
Design
and
Analysis
of
Algorithms
I
Prerequisites
Watch
this
aBer:
• QuickSort
-‐
Par..oning
around
a
pivot
• QuickSort
–
Choosing
a
good
pivot
• Probability
Review,
Part
I
Tim
Roughgarden
The
Problem
For
simplicity
Input
:
array
A
with
n
dis.nct
numbers
and
a
number
Output
:
ith
order
sta.s.c
(i.e.,
ith
smallest
element
of
input
array)
Example
:
median.
3rd
order
sta.s.c
(
i
=
(n+1)/2
for
n
odd,
i
=
n/2
for
n
even
)
Tim
Roughgarden
Reduc.on
to
Sor.ng
O(nlog(n))
algorithm
1) Apply
MergeSort
2)
return
ith
element
of
sorted
array
Fact
:
can’t
sort
any
faster
[
see
op.onal
video
]
Next
:
O(n)
.me
(randomized)
by
modifying
Quick
Sort.
Op.onal
Video
:
O(n)
.me
determinis.c
algorithm.
-‐-‐
pivot
=
“median
of
medians”
(warning
:
not
prac.cal
)
Tim
Roughgarden
Par..oning
Around
a
Pivot
Key
Idea
:
par..on
array
around
a
pivot
element.
-‐Pick
element
of
array
pivot
-‐Rearrange
array
so
that
-‐LeB
of
pivot
=>
less
than
pivot
-‐Right
of
pivot
=>
greater
than
pivot
>
pivot
<
pivot
Note
:
puts
pivot
in
its
“righbul
posi.on”.
Tim
Roughgarden
Tem
ver
Suppose
we
are
looking
for
the
5th
order
sta.s.c
in
an
input
array
of
length
10.
We
par..on
the
array,
and
the
pivot
winds
up
in
the
third
posi.on
of
the
par..oned
array.
On
which
side
of
the
pivot
do
we
recurse,
and
what
order
sta.s.c
should
we
look
for?
The
3rd
order
sta.s.c
on
the
leB
side
of
the
pivot.
The
2nd
order
sta.s.c
on
the
right
side
of
the
pivot.
The
5th
order
sta.s.c
on
the
right
side
of
the
pivot.
Randomized
Selec.on
Rselect
(array
A,
length
n,
order
sta.s.c
i)
0)
if
n
=
1
return
A[1]
1) Choose
pivot
p
from
A
uniformly
1st
part
2nd
part
at
random
jth
posi.on
2) Par..on
A
around
p
let
j
=
new
index
of
p
3) If
j
=
i,
return
p
4) If
j
>
i,
return
Rselect(1st
part
of
A,
j-‐1,
i)
5) [if
j<i]
return
Rselect
(2nd
part
of
A,
n-‐j,
i-‐j)
Tim
Roughgarden
Proper.es
of
RSelect
Claim
:
Rselect
is
correct
(guaranteed
to
output
ith
order
sta.s.c)
Proof
:
by
induc.on.
[like
in
op.onal
QuickSort
video]
Running
Time
?
:
depends
on
“quality”
of
the
chosen
pivots.
Tim
Roughgarden
Tem
ver
What
is
the
running
.me
of
the
RSelect
algorithm
if
pivots
are
always
chosen
in
the
worst
possible
way?
Example
:
-‐-‐
suppose
i
=
n/2
-‐-‐
suppose
choose
pivot
=
minimum
every
.me
=>
.me
in
each
of
recursive
calls
Running
Time
of
RSelect?
Running
Time
?
:
depends
on
which
pivots
get
chosen.
(could
be
as
bad
as
)
Key
:
find
pivot
giving
“balanced”
split.
Best
pivot:
the
median
!
(but
this
is
circular)
⇒Would
get
recurrence
⇒
T(n)
=
O(n)
[
case
2
of
Master
Method
]
Hope
:
random
pivot
is
“premy
good”
“oBen
enough”
Tim
Roughgarden
Running
Time
of
RSelect
Rselect
Theorem
:
for
every
input
array
of
length
n,
the
average
running
.me
of
Rselect
is
O(n)
-‐-‐
holds
for
every
input
[no
assump.ons
on
data]
-‐-‐
“average”
is
over
random
pivot
choices
made
by
the
algorithm
Tim
Roughgarden
