Randomized Quickselect and Randomized Quicksort
Nishant Mehta Lecture 15 – Part II
http://xkcd.com/1185
Recall Quickselect’s “Recursion Path”
Goal: Select the 6th smallest element
15 elements
7 elements
7 elements
S
pivot0
pivot0
pivot0
Recall Quickselect’s “Recursion Path”
Goal: Select the 6th smallest element
15 elements
S
7 elements
pivot0
pivot0
7 elements
pivot0
Recall Quickselect’s “Recursion Path”
Goal: Select the 6th smallest element
15 elements
7 elements
pivot0
pivot0
7 elements
S
pivot0
8th smallest element and larger
Recall Quickselect’s “Recursion Path”
Goal: Select the 6th smallest element
15 elements
S
Prune!
7 elements
pivot0
pivot0
7 elements
pivot0
8th smallest element and larger
Recall Quickselect’s “Recursion Path”
Goal: Select the 6th smallest element
15 elements
Prune!
7 elements
pivot0
pivot0
7 elements
Quickselect with k=6
8th smallest element and larger
S
pivot0
Recall Quickselect’s “Recursion Path”
Goal: Select the 6th smallest element
15 elements
7 elements
pivot0
pivot0
7 elements
pivot0
3 elements
3 elements
pivot1
pivot1
pivot1
S
Recall Quickselect’s “Recursion Path”
Goal: Select the 6th smallest element
15 elements
7 elements
pivot0
pivot0
7 elements
pivot0
S
3 elements
pivot1
pivot1
3 elements
pivot1
Recall Quickselect’s “Recursion Path”
Goal: Select the 6th smallest element
15 elements
7 elements
pivot0
pivot0
7 elements
pivot0
S
3 elements
pivot1
pivot1
3 elements
pivot1
4th smallest element and smaller
Recall Quickselect’s “Recursion Path”
Goal: Select the 6th smallest element
15 elements
7 elements
pivot0
pivot0
7 elements
Prune!
pivot0
S
3 elements
pivot1
pivot1
3 elements
pivot1
4th smallest element and smaller
Recall Quickselect’s “Recursion Path”
Goal: Select the 6th smallest element
15 elements
7 elements
pivot0
pivot0
7 elements
Prune!
pivot0
S
3 elements
pivot1
pivot1
3 elements
pivot1
4th smallest element and smaller
Quickselect with k=(6-4)=2
(Recall) Upper bound on runtime of Quickselect with median of medians pivot
Theorem
Quickselect(S,k) using the median of medians pivot returns the kth order statistic in time at most O(n).
“But Quickselect with the median of medians pivots seemed rather complicated. Wouldn’t it be simpler to just use a random pivot?”
Randomized Quickselect
Quickselect(S, k): If S.length() == 1
Return S[0]
p = RandomPivot(S) // p will be a random element from S [L, G] = Partition(S, p)
If k <= length(L)
Return Quickselect(L, k) ElseIf k == (length(L) + 1)
Return p
Else // k > (length(L) + 1)
Return Quickselect(G, k – length(L) – 1)
Picking a good pivot
If the random pivot falls within blue middle region, the size of the next node in the recursion path will be at most 3/4 the size of the current node.
Using the language from last lecture, such a pivot is a β-approximate median for = 3/4
Picking a good pivot
probability of falling in this region is 1/2
If the random pivot falls within blue middle region, the size of the next node in the recursion path will be at most 3/4 the size of the current node.
Using the language from last lecture, such a pivot is a β-approximate median for = 3/4
Sketch of bound on expected runtime
•
•
Let’s view the extension of the recursion path in rounds
In each round, we draw a new pivot and consequently add one node in our recursion path (highlighted in blue below)
pivot0
pivot0
pivot0
S
pivot1
pivot1
pivot1
Sketch of bound on expected runtime
•
•
•
•
•
Let’s view the extension of the recursion path in rounds
In each round, we draw a new pivot and consequently add one node in our recursion path (highlighted in blue below)
Because the chance of a random pivot falling in the region of good pivots is 1/2, in roughly half the rounds we expect to decrease the node size by a factor 3/4
After k rounds of good pivots, the node size is only n(3/4)k
After log4/3 n rounds of good pivots, the node size is at most 1 and so the algorithm has returned
Sketch of bound on expected runtime
•
Quickselect with the median of medians pivot was
The expected runtime should therefore be at most double the runtime of an algorithm that always gets good pivots
•
precisely such an algorithm
The expected runtime of Ran+domized Quickselect should be O(n)
Analysis
R ecu-rsion
→n→D→D-→O→ a-
1st node
epoch
0 epoch I
– be # elements Let Xi
in
node i
only need
(
+.
n )
sound time,
bound Ef x,]
X= ,
toomer
Epochs idea :
–
consists of those nudes sit t n a X
Epoch O
En “‘
(¥1.n <
Epoch
"
'n it'
Epoch Epoch
2 j
"
in
< -n
Xi E axis
w e
" l
"
"
⇒
in
.
,
Xie Yan
--
.
.
IEC
E.
Xi )
=
Ef Io !)
?n÷÷i Ioi?
El
.
i Y
--
n:o c .is :
ut!e::;;
: IE[¥oY;-⇐I.n) fiXi
=
= n off,)iIE(
VT
is : Yi is
random random
variable urine
y; )
Let's upper bound E [Y;) ⇐ expected length of epoch j
f
t; I
Tidd:!:! I bad ⇐ not gone
#
of random pivot choices until w e get a
in the middle half
pivot Msoodnirotl
; ¥%occurs)
=
Y;) e Ef# of coin flies until IE
first
'
(
=
¥%
-
PCT) =p t pay, = ,- p
THI t . . - .
until
first
P(THI t
occurs)
Ef =
l
= Ika-rip"" g= emftp.I.pk) KH ,
flies
of
t2
coin
#
Ht
3 PCT
'
I
-
.
'
P
(t
(
CI-plt2 -pl- p
t
3-
(t-
pl p
t
.--
= g- pi
% KI
E.
Kpk" =d- plat Ip- I []
-- t h a t,
-
an
dapfp'T
thrift
= =
Y÷ep
=
2
ii.
i
IE --
Xi )
=
Ef Y
Io
?n÷÷;i ) utn%e::;;
El
IE[¥oY;-⇐I.n) fiXi
Eoin :D:
=
:
is Yi is
random random
variable urine
i
= n,§ IE(
ti
:
, 2h
y; ÷)
=8n
, ()EC- 8h=
2-
I
§, =
2n ¥= 2n'4 .
runtime
Ocn)
IE
Randomized Quicksort
Quicksort(S, p, r): If p < r
q = Partition(S, p, r) Quicksort(S, p, q - 1) Quicksort(S, q + 1, r)
Randomized Quicksort - Last Element as Pivot
Partition(S, p, r): x = S[r]
i =p - 1
For j = p to r - 1
If S[j] <= x i =i + 1
Swap(S[i], S[j]) Swap(S[i+1], S[r])
Return i + 1
Loop invariant
For any index k:
If p k i, then S[k] x
If i+1 k j-1, then S[k] > x If k = r, then A[k] = x
Randomized Quicksort – Random Pivot
Partition(S, p, r):
Swap(S[Random(p, r)], S[r])
x = S[r] // the last element is now random i =p – 1
For j = p to r – 1
Loop invariant
If S[j] <= x i =i + 1
Swap(S[i], S[j]) Swap(S[i+1], S[r])
Return i + 1
For any index k:
If p k i, then S[k] x
If i+1 k j-1, then S[k] > x If k = r, then A[k] = x
Analysis
Bound runtime
of
(
Quicksort
n
by counting # comparisons between elements)
t w o
elements
total randomized
( b/c
Quicksort) ⇒
# is
comparisons random
–
–
random
Let X be total # of comparisons
” X
pivot is
random
variable elements
then ” Faeth 2 elements ( ith and 4thone , e.g. ) can !ypμt
at most once 1 .
the pivot .
-F a ct
compared
I
‘ .
If
2
are
compared ,
one
is
exactly
-From Facts /&2: ‘
! “nitin..”
×
T
.–i
Z, 1¥
–
,
=/if is
off-ref ,
Zz tZs
Zn
Zz
=
Ei indicator
Ei. random
%. variable
S
L
.
.
..
L
Zn compared to
runtime,
we bound !E. ) I” ii
average – case
TECH = IEEE * xik =
To
? .
;μElXi
fo Zj
if z; is never
z ,
=
fr ( Z ; is compared 2- k
)
fr ( Z ; is compared Zk ) – how to upper hand ?
can -2;becomparedtoZk?
Z; compared to -2k) → (Z; is pivot or Z, is pivot)
When [
⇒
[ one
,
tifits,. .- i-2k-i.Zk]
Suppose
o f 44
elemggntp.g.to
i n
some
call to
partition,
o n e
Zj , Zjt,
Zk
pivot
,…,
is
Suppose -in some
is
4
call to
partition,
o n e
o f
Zj , Zjt,
Zk
4
,…,
pivot
”
Pr( ti or Zk is selected as pivot given that one of Z;→k 2- is selectas pivot
–
Z, → k )
==2- IZj→KI k- jtl
iii.ii. i
.
.
‘
.
uncle ÷÷*
ii.
=
a ”
”
e
I
=
E =
2(n- it
E
k = 22
k
un- H
,
xtdx
S
Un- it(logxl!= E2a
Un- it
=
logy
log n 0(n logn)