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