CS计算机代考程序代写 algorithm Randomized Quickselect and Randomized Quicksort

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)