n - Bilkent University Computer Engineering Department

CS473-Algorithms I
Lecture 6-b
Randomized QuickSort
CS473 – Lecture 6-b
Cevdet Aykanat - Bilkent University
Computer Engineering Department
1
Randomized Quicksort
• Average-case assumption:
– all permutations are equally likely
– cannot always expect to hold
• Alternative to assuming a distribution: Impose a
distribution
–Partition around a random pivot
CS473 – Lecture 6-b
Cevdet Aykanat - Bilkent University
Computer Engineering Department
2
Randomized Quicksort
Typically useful when
– there are many ways that an algorithm can proceed
– but, it is difficult to determine a way that is guaranteed
to be good.
– Many good alternatives; simply choose one randomly
• Running time is independent of input ordering
• No specific input causes worst-case behavior
• Worst case determined only by output of random
number generator
CS473 – Lecture 6-b
Cevdet Aykanat - Bilkent University
Computer Engineering Department
3
Randomized Quicksort
R-QUICKSORT(A, p, r)
if p < r then
q ← R-PARTITION(A, p, r)
R-QUICKSORT(A, p, q)
R-QUICKSORT(A, q+1, r)
R-PARTITION(A, p, r)
s ← RANDOM(p, r)
exchange A[p] ↔ A[s]
return H-PARTITION(A, p, r)
exchange A[r] ↔ A[s]
return L-PARTITION(A, p, r)
for Lomuto’s partitioning
• Permuting whole array also works well on the average
– more difficult to analyze
CS473 – Lecture 6-b
Cevdet Aykanat - Bilkent University
Computer Engineering Department
4
Formal Average - Case Analysis
• Assume all elements in A[p…r] are distinct
• n=r−p+1
• rank(x) =|{A[i]: p ≤ i ≤ r and A[i] ≤ x}|
• “exchange A[p]↔x = A[s]” (x  A[p…r] random pivot)
 P(rank(x)=i)=1/n,
CS473 – Lecture 6-b
for i=1,2,…, n
Cevdet Aykanat - Bilkent University
Computer Engineering Department
5
Likelihood of Various Outcomes of
Hoare’s Partitioning Algorithm
• rank(x) =1 :
k =1 with i1=j1=p  L1={A[p]=x}
 |L| =1
x = pivot
• rank(x) >1 :  k >1
– iteration 1: i1=p, p < j1 ≤ r  A[p]↔x =A[j1]
 pivot x stays in the right region
– termination: Lk={A[i]: p ≤ i ≤ r and A[i]<x}
 |L|= rank(x) −1
CS473 – Lecture 6-b
Cevdet Aykanat - Bilkent University
Computer Engineering Department
6
Various Outcomes
• rank(x) =1 :  |L|=1
• rank(x) >1 :  |L|= rank(x) - 1
x = pivot
• P(|L|=1) = P(rank(x) =1) + P(rank(x) =2)
=1/n + 1/n = 2/n
• P(|L|=i)=P(rank(x) =i+1)
=1/n
CS473 – Lecture 6-b
for i=2,…,n −1
Cevdet Aykanat - Bilkent University
Computer Engineering Department
7
Average - Case Analysis: Recurrence
T(n) =
+
+
x = pivot
2
3
+
1
(T(i)+T(n−i))
n
i+1
+
1
(T(n-1)+T(1))
n
n
+
CS473 – Lecture 6-b
1 (T(1)+T(n−1))
n
1 (T(1)+T(n−1))
n
1 (T(2)+T(n−2))
n
rank(x)
1
(n)
Cevdet Aykanat - Bilkent University
Computer Engineering Department
8
Recurrence
1
T(n) = n
n 1

(T(q)+T(n-q)) + 1 (T(1)+T(n−1)) + (n)
n
q 1
- but, 1 (T(1)+T(n-1)) =
n
T(n) = 1
n
1
((1)+ O(n2)) = O(n)
n
n 1
(T(q)+T(n-q)) + (n)
q 1
• for k = 1,2,…,n−1 each term T(k) appears twice
–once for q = k and once for q = n−k
n 1
• T(n) = 2
n
CS473 – Lecture 6-b
T(k) + (n)
k 1
Cevdet Aykanat - Bilkent University
Computer Engineering Department
9
Solving Recurrence: Substitution
Guess: T(n)=O(nlgn)
I.H. : T(k) ≤ aklgk + b  k<n, for some constants a > 0 and b ≥ 0
2
T(n) =
n
 2
n
n 1
T(k) + (n)
k 1
n 1

(aklgk + b) + (n)
k 1
n 1
= 2a
n

2a
n

(klgk + b) + 2b (n-1) +(n)
n
k 1
n 1
klgk + (2b) +(n)
k 1
Need a tight bound for  klgk
CS473 – Lecture 6-b
Cevdet Aykanat - Bilkent University
Computer Engineering Department
10
Tight bound for  klgk
• Bounding the terms
n 1
n 1
k 1
k 1
klgk   nlgn = n (n-1) lgn  n2 lgn
This bound is not strong enough because
• T(n) 
=
2a 2
n lgn + 2b +(n)
n
2anlgn + 2b + Θ(n)
CS473 – Lecture 6-b
Cevdet Aykanat - Bilkent University
Computer Engineering Department
11
Tight bound for  klgk
• Splitting summations: ignore ceilings for simplicity
n 1
klgk
k 1

n / 2 1
n 1
k 1
k n / 2
klgk +  klgk
First summation:
lgk < lg(n/2) = lgn−1
Second summation:
lgk < lgn
CS473 – Lecture 6-b
Cevdet Aykanat - Bilkent University
Computer Engineering Department
12
n 1
n / 2 1
n 1
k 1
k 1
k n / 2
Splitting:  k lg k   k lg k   k lg k
n 1
n / 2 1
n 1
k 1
k 1
k n / 2
 k lg k (lg n  1)  k  lg n  k
n 1
n / 2 1
1
1n n
 lg n k   k  n(n  1) lg n 
(  1)
2
22 2
k 1
k 1
1 2
1 2 1
 n lg n  n  n(lg n  1 / 2)
2
8
2
n 1
1 2
1 2
k lg k  n lg n  n for lg n  1 / 2  n  2

2
8
k 1
CS473 – Lecture 6-b
Cevdet Aykanat - Bilkent University
Computer Engineering Department
13
Substituting:
n 1
1 2
1 2
k lg k  n lg n  n

2
8
k 1
2a n 1
T ( n) 
k lg k  2b  (n)

n k 1
2a 1 2
1 2

( n lg n  n )  2b  (n)
n 2
8
a

 an lg n  b   n  ((n)  b) 
4

a
We can choose a large enough so that
n  (n)  b
4
 T (n)  an lg n  b  T (n)  O(n lg n)
CS473 – Lecture 6-b
Cevdet Aykanat - Bilkent University
Computer Engineering Department
Q.E.D.
14