Quick Sort
Quicksort
A[p…q] ≤ A[q+1…r]
• Sort an array A[p…r]
• Divide
– Partition the array A into 2 subarrays A[p..q] and A[q+1..r],
such that each element of A[p..q] is smaller than or equal to
each element in A[q+1..r]
– Need to find index q to partition the array
2
Quicksort
A[p…q] ≤ A[q+1…r]
• Conquer
– Recursively sort A[p..q] and A[q+1..r] using
Quicksort
• Combine
– Trivial: the arrays are sorted in place
– No additional work is required to combine them
– The entire array is now sorted
3
QUICKSORT
Alg.: QUICKSORT(A, p, r) Initially: p=1, r=n
if p < r
then q PARTITION(A, p, r)
QUICKSORT (A, p, q)
QUICKSORT (A, q+1, r)
Recurrence:
T(n) = T(q) + T(n – q) + f(n) PARTITION())
4
Partitioning the Array
• Choosing PARTITION()
– There are different ways to do this
[Link] pick first element as pivot.
[Link] pick last element as pivot
[Link] a random element as pivot.
[Link] median as pivot.
– Each has its own advantages/disadvantages
5
Partitioning the Array
• Choosing PARTITION()
– There are different ways to do this
– Each has its own advantages/disadvantages
• Hoare partition (see prob. 7-1, page 159)
– Select a pivot element x around which to partition
– Grows two regions
A[p…i] x x A[j…r]
A[p…i] x
x A[j…r]
i j
6
Example
pivot x=5 A[p…r]
5 3 2 6 4 1 3 7
5 3 2 6 4 1 3 7
i j
i j
3 3 2 6 4 1 5 7
3 3 2 6 4 1 5 7
i j
i j
3 3 2 1 4 5 6 7
3 3 2 5 4 1 6 7
i j
i j A[p…q] A[q+1…r]
3 3 2 1 4 5 6 7
3 3 2 1 4 5 6 7
i j
j i 7
Example
A[p…q] A[q+1…r]
3 3 2 1 4 5 6 7
8
Example
A[p…q] A[q+1…r]
3 3 2 1 4 5 6 7
9
Partitioning the Array
Alg. PARTITION (A, p, r)
p r
1. x A[p]
A: 5 3 2 6 4 1 3 7
2. i p – 1
3. j r + 1 i j
A[p…q] ≤ A[q+1…r]
4. while TRUE
5. do repeat j j – 1 A: ap ar
6. until A[j] ≤ x
j=q i
7. do repeat i i + 1
8. until A[i] ≥ x
Each element is
9. if i < j visited once!
10. then exchange A[i] A[j] Running time: (n)
n=r–p+1
11. else return j
10
Recurrence
Initially: p=1, r=n
Alg.: QUICKSORT(A, p, r)
if p < r
then q PARTITION(A, p, r)
QUICKSORT (A, p, q)
QUICKSORT (A, q+1, r)
Recurrence:
T(n) = T(q) + T(n – q) + n
11
Worst Case Partitioning
• Worst-case partitioning
– One region has one element and the other has n – 1 elements
– Maximally unbalanced
n n
• Recurrence: q=1 1 n-1 n
1 n-2 n-1
T(n) = T(1) + T(n – 1) + n, n-2
n 1 n-3
T(1) = (1) 1
2 3
T(n) = T(n – 1) + n 1 1 2
n
n k 1 (n) (n 2 ) (n 2 ) (n2)
= k 1
When does the worst case happen? 12
Best Case Partitioning
• Best-case partitioning
– Partitioning produces two regions of size n/2
• Recurrence: q=n/2
T(n) = 2T(n/2) + (n)
T(n) = (nlgn) (Master theorem)
13
Case Between Worst and Best
• 9-to-1 proportional split
Q(n) = Q(9n/10) + Q(n/10) + n
14
How does partition affect performance?
15
How does partition affect performance?
16
Performance of Quicksort
• Average case
– All permutations of the input numbers are equally likely
– On a random input array, we will have a mix of well balanced
and unbalanced splits
– Good and bad splits are randomly distributed across throughout
the tree
partitioning cost:
n combined partitioning cost: n n = (n)
1 n-1 2n-1 = (n)
(n – 1)/2 + 1 (n – 1)/2
(n – 1)/2 (n – 1)/2
Alternate of a good Nearly well
and a bad split balanced split
• Running time of Quicksort when levels alternate
between good and bad splits is O(nlgn)
17