DESIGN AND ANALYSIS OF

ALGORITHM

Quicksort, Randomized
Prepared by Algorithms
Murari Kumar Singh
Quicksort, Randomized
Algorithms
 Quicksort
• Proposed by C.A.R. Hoare in 1962.
• Divide-and-conquer algorithm.
• Sorts “in place” (like insertion sort, but not
like merge sort).
• Very practical (with tuning).
 Divide and conquer
Quicksort an n-element array:
1. Divide: Partition the array into two subarrays
around a pivot x such that elements in lower
subarray  x  elements in upper subarray.
x x x
2. Conquer: Recursively sort the two subarrays.
3. Combine: Trivial.
Key: Linear-time partitioning subroutine.
 Partitioning subroutine
PARTITION(A, p, q) ⊳ A[ p . .
q] x  A[ p] ⊳ pivot = Running time
iA[p]p = O(n) for n
for j  p + 1 to q elements.
do if A[ j]  x
then ii+1
exchange A[i] 
A[ j] exchange A[ p]  A[i]
return i

Invariant: x x x ?
p i j
Example of partitioning

6 10 13 5 8 3 2 11
i j
Example of partitioning

6 10 13 5 8 3 2 11
i j
Example of partitioning

6 10 13 5 8 3 2 11
i j
Example of partitioning

6 10 13 5 8 3 2 11
6 5 13 10 8 3 2 11
i j
Example of partitioning

6 10 13 5 8 3 2 11
6 5 13 10 8 3 2 11
i j
Example of partitioning

6 10 13 5 8 3 2 11
6 5 13 10 8 3 2 11
i j
Example of partitioning

6 10 13 5 8 3 2 11
6 5 13 10 8 3 2 11

6 5 3 10 8 13 2 11
i j
Example of partitioning

6 10 13 5 8 3 2 11
6 5 13 10 8 3 2 11

6 5 3 10 8 13 2 11
i j
Example of partitioning

6 10 13 5 8 3 2 11
6 5 13 10 8 3 2 11

6 5 3 10 8 13 2 11

6 5 3 2 8 13 10 11
i j
Example of partitioning

6 10 13 5 8 3 2 11
6 5 13 10 8 3 2 11

6 5 3 10 8 13 2 11

6 5 3 2 8 13 10 11
i j
Example of partitioning

6 10 13 5 8 3 2 11
6 5 13 10 8 3 2 11

6 5 3 10 8 13 2 11

6 5 3 2 8 13 10 11
i j
Example of partitioning

6 10 13 5 8 3 2 11
6 5 13 10 8 3 2 11

6 5 3 10 8 13 2 11

6 5 3 2 8 13 10 11

2 5 3 6 8 13 10 11
i
Pseudocode for quicksort
QUICKSORT(A, p, r)
if p < r
then q  PARTITION(A, p, r)
QUICKSORT(A, p, q)
QUICKSORT(A, q+1, r)

Initial call: QUICKSORT(A, 1, n)

 Analysis of quicksort

• Assume all input elements are distinct.

• In practice, there are better partitioning
algorithms for when duplicate input
elements may exist.
• Let T(n) = worst-case running time on
an array of n elements.
 Worst-case of quicksort
• Input sorted or reverse sorted.
• Partition around min or max element.
• One side of partition always has no elements.
T (n)  T (0)  T (n 1)  (n)
 (1)  T (n 1)  (n)
 T (n 1)  (n)
 (n2 ) (arithmetic series)
Worst-case recursion tree
T(n) = T(0) + T(n–1) + cn
Worst-case recursion tree
T(n) = T(0) + T(n–1) +
cn T(n)
 Worst-case recursion tree
T(n) = T(0) + T(n–1) + cn
cn
T(0) T(n–1)
 Worst-case recursion tree
T(n) = T(0) + T(n–1) + cn
cn
T(0) c(n–1)
T(0) T(n–2)
 Worst-case recursion tree
T(n) = T(0) + T(n–1) + cn
cn
T(0) c(n–1)
T(0) c(n–2)
T(0) 

(1)
 Worst-case recursion tree
T(n) = T(0) + T(n–1) + cn
cn 
 n
T(0) c(n–1)   k   n2
k
T(0) c(n–  1
2)

T(0)
(1)
 Worst-case recursion tree
T(n) = T(0) + T(n–1) + cn
cn 
 n
(1) c(n–   k   n2
1) k
(1) c(n–  1
h = n 2) T(n) = (n) + (n2)
(1)  = (n2)

(1)
 Best-case analysis
(For intuition only!)
If we’re lucky, PARTITION splits the array evenly:
T(n) = 2T(n/2) + (n)
= (n lg n) (same as merge sort)

What if the split is always 101 : 10

9
?
T (n)  T 101 n T 9 n
10
(n)
What is the solution to this recurrence?
Analysis of “almost-best” case
T
(n)
Analysis of “almost-best” case
cn
T 101 T 109
n n
 Analysis of “almost-best” case
cn
1 cn
10 9 cn
10

T 100
1
n T 100
9 T 9
100
n T 100
81
n  n
 Analysis of “almost-best” case
cn cn
1 cn
10 9 cn
10
log10/9n
1
cn 9
cn 9 cn 81 cn
cn
cn
100 100 100 100

…
(1) O(n) leaves
(1)
 Analysis of “almost-best” case
cn cn
1 cn
10 9 cn
log10 10
log10/9n
n100
1 cn 9 cn 9 cn 81 cn
cn
cn
100 100 100

…
(1) O(n) leaves

(n lg (1)
n) cn log10n  T(n)  cn log10/9n +
Lucky! (n)
 More intuition
Suppose we alternate lucky, unlucky,
lucky, unlucky, lucky, ….
L(n) = 2U(n/2) + (n) lucky
U(n) = L(n – 1) + unlucky
(n)
Solving:
L(n) = 2(L(n/2 – 1) + (n/2)) +
(n)
(n lg n)
= 2L(n/2 + (n)
– 1)Lucky!
How can we make sure we are usually lucky?
THANK YOU
Next Session:
Randomize Quick Sort
 Randomized quicksort
IDEA: Partition around a random element.
• Running time is independent of the input
order.
• No assumptions need to be made about
the input distribution.
• No specific input elicits the worst-case
behavior.
• The worst case is determined only by the
output of a random-number generator.
 Randomized quicksort
analysis
Let T(n) = the random variable for the running
time of randomized quicksort on an input of size
n, assuming random numbers are independent.
For k = 0, 1, …, n–1, define the indicator
random variable
1 if PARTITION generates a k : n–k–1
Xk =
split,
E[Xk] =0Pr{X
otherwise.
k = 1} = 1/n, since all splits are
equally likely, assuming elements are distinct.
 Analysis (continued)
T(0) + T(n–1) + (n) if 0 : n–1
split,
T(n) =
T(1) +MT(n–2) + (n) if 1 : n–2
split, + T(0) + (n) if n–1 : 0
T(n–1)
n
split,
1
  X k T (k )  T (n  k 1) 
(n).
k 0
 Quicksort in practice
• Quicksort is a great general-
purpose sorting algorithm.
• Quicksort is typically over twice as fast
as merge sort.
• Quicksort can benefit substantially
from
code tuning.
• Quicksort behaves well even with
caching and virtual memory.