Quick Sort

Introduction to Algorithms 31
88 52
14
25 98 30
62 23
79

Divide and Conquer

Chapter 7: Quick Sort

2

Quick Sort Quick Sort

14 88
98
Partition set into two using 30 ≤ 52 ≤ 62
31
randomlyy chosen ppivot 25 23 79

88 52
14
31
25 98 30 sort the first half. sort the second half.
62 23
79
14,23,25,30,31 62,79,98,88
14 88
98
31 30 ≤ 52 ≤ 62
25 23 79

3 4
Quick Sort Quicksort
„ Quicksort advantages:
14 23 25 30 31
14,23,25,30,31 ‰ Sorts in place
52 ‰ Sorts O(n lg n) in the average case
62 79 88 98
62,79,88,98 ‰ Very efficient in practice

„ Quicksort disadvantages :
‰ Sorts O(n2) in the worst case
Glue pieces together. ‰ not stable
(No real work) „ Does not preserve the relative order of elements with equal
keys
„ Sorting algorithm (stable) if 2 records with same key stay in
14,23,25,30,31,52,62,79,88,98 original order
‰ But in practice, it’s quick
‰ And the worst case doesn’t happen
pp often … sorted

5 6

Quicksort Quicksort
„ Another divide-and-conquer
q algorithm:
g „ The basic algorithm to sort an array A
„ Divide: A[p…r] is partitioned (rearranged) into consists
i t off the
th following
f ll i ffour easy steps:
t
two nonempty y A[p…q-1]] and A[q+1…r]
p y subarrays ‰ If the number of elements in A is 0 or 1, then
s.t. each element of A[p…q-1] is less than or return
t
equal to each element of A[q+1…r]. Index q is ‰ Pick any element v in A. This is called the pivot
computed here, called pivot. ‰ Partition A-{v} (the remaining elements in A) into
two disjoint groups:
„ Conquer: two subarrays are sorted by recursive „ A1 = {x ∈ A-{{v} | x ≤ v},
} and
d
calls to quicksort. „ A2 = {x ∈ A-{v} | x ≥ v}
‰ return
„ Combine: unlike merge sort, no work needed „ {quicksort(A1) followed by v followed by
since the subarrays are sorted in place already. quicksort(A2)}

7 8
Quicksort Example
„ Small instance has n ≤ 1
‰ Every small instance is a sorted instance
„ To sort a large instance: 6 2 8 5 11 10 4 1 9 7 3
‰ select a pivot element from out of the n elements
„ Partition the n elements into 3 groups left, Use 6 as the pivot
middle and right
‰ The middle group contains only the pivot element
‰ All elements in the left group are ≤ pivot
‰ All elements in the right group are ≥ pivot 2 5 4 1 3 6 7 9 10 11 8
„ Sort left and right groups recursively
„ Answer is sorted left group, followed by middle Sort left and right groups recursively
group followed by sorted right group
9 10

Quicksort Code Partition

Quicksort(A, p, r) „ Clearly, all the action takes place in the
Clearly
{ partition() function
if (p
p < r)
{ ‰ Rearranges the subarray in place
q = Partition(A, p, r)
Quicksort(A, p , q-1) ‰ End result:
Quicksort(A, q+1 , r) „ Two subarrays
} „ All values in first subarray ≤ all values in second
}
‰ Returns the index of the “pivot” element
separating the two subarrays
„ Initial call is Quicksort(A, 1, n), where n in the
length of A

11 12
Partition Code Partition Example A = {2,
{2 8,
8 7,
7 1,
1 3,
3 5,
5 6,
6 4}
i pj r pi j r
Partition(A, p, r)
{ 2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4
x = A[r] // x is pivot
i = p - 1 pi j r pi j r
for j = p to r – 1
{
2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4
do if A[j]
[j] <= x
then p i j r p i j r
{ 2 1 7 8 3 5 6 4 2 11 33 8 7 5 6 4
i = i + 1
exchange A[i] ↔ A[j] p i j r p i r
}
} 2 11 33 8 7 5 6 4 2 11 33 8 7 5 6 4
exchange A[i+1] ↔ A[r]
return i+1 partition() runs in O(n) time p i r
}
2 11 33 4 7 5 6 8
13 14

Partition Example Explanation Choice Of Pivot

„ Red shaded elements are in the first partition „ Pivot is the rightmost element in list that is
with values ≤ x (pivot) to be sorted
‰ When sorting A[6:20],
6 20 use A[20]
20 as the pivot
„ Gray shaded elements are in the second
partition with values ≥ x
p (pivot))
(p ‰ Textbook implementation does this

„ The unshaded elements have no yet been „ Randomly select one of the elements to be
put in one of the first two partitions sorted as the pivot
‰ When sorting g A[[6:20],
], generate
g a random number
„ The final white element is the pivot r in the range [6, 20]
‰ Use A[r] as the pivot

15 16
Choice Of Pivot Choice Of Pivot
„ Median of Three rule - from the leftmost,
Median-of-Three leftmost middle
middle, „ When the pivot is picked at random or when
and rightmost elements of the list to be sorted,
select the one with median key as the pivot
the median-of-three rule is used, we can use
th quicksort
the i k t code th textbook
d off the t tb k provided,
id d
When sorting A[6:20], examine A[6], A[13] ((6+20)/2), and
‰
A[20] we first swap the rightmost element and the
chosen
h pivot.
i t
‰ Select the element with median (i.e., middle) key
swap
‰ If A[6].key = 30, A[13].key = 2, and A[20].key = 10, A[20]
becomes the pivot

‰ If A[6].key = 3, A[13].key = 2, and A[20].key = 10, A[6]

becomes the pivot
pivot
17 18

Runtime of Quicksort Worst Case Partitioning

The running g time of q
quicksort depends
p on whether the
„ Worst case: „
partitioning is balanced or not.
‰ every time nothing to move
„ Θ(n) time to partition an array of n elements
‰ pivot = left (right) end of subarray
‰ Θ(n2) „ Let T(n) be the time needed to sort n elements
0123456789 „ T(0) = T(1) = c, where c is a constant
0 123456789 „ When n > 1,
Wh 1
n ‰ T(n) = T(|left|) + T(|right|) + Θ(n)

89 „ T(n) is maximum (worst-case) when either |left| = 0 or |right| = 0

following each partitioning
8 9

19 20
Worst Case Partitioning Worst Case Partitioning
„ Worst-Case Performance (unbalanced):
‰ T(n) = T(1) + T(n-1) + Θ(n)
„ partitioning takes Θ(n)
‰ = (2 + 3 + 4 + …+ n-1 + n) + n =
‰ = ∑k = 2 to nΘ((k) + n = Θ(( ∑k = 2 to nk) + n = Θ((n2)

„ This occurs when

‰ the input is completely sorted
„ or when
o e
‰ the pivot is always the smallest (largest) element

21 22

Best Case Partition Best Case Partitioning

„ When the partitioning procedure produces
two regions of size n/2, we get a balanced
partition
titi with
ith best
b t case performance:
f
‰ T(n) = 2T(n/2) + Θ(n) = Θ(n lg n)

„ Average complexity is also Θ(n lg n)

23 24
Average Case Average Case
T (n) = T (n /10) + T (9n /10) + Θ(n) = Θ(n log n)!
„ Assuming random input
input, average-case running time
is much closer to Θ(n lg n) than Θ(n2)

„ First, a more intuitive explanation/example:

‰ S ppose that partition() always
Suppose al a s prod
produces
ces a 9-to-1
9 to 1
proportional split. This looks quite unbalanced!
‰ The recurrence is thus:
T(n) = T(9n/10) + T(n/10) + Θ(n) = Θ(n lg n)
F a split
For lit α, where
li off proportionality
ti h 0≤α≤½,
≤½ the
h minimum
i i depth
d h
‰ How deep will the recursion go? of the tree is - lg n / lg α & the maximum depth is - lg n / lg(1-α).
log2n = log10n/log102

25 26

Average Case Average Case

„ Everyy level of the tree has cost cn, until a boundaryy „ What happens if we bad-split root node, then good-split the
condition is reached at depth log10 n = Θ( lgn), and then resulting size (n -1) node?
the levels have cost at most cn. ‰ We end up with three subarrays, size
1 (n-1)/2,
„ 1, 1)/2 (n-1)/2
1)/2
„ The recursion terminates at depth log10/9 n= Θ(lg n). ‰ Combined cost of splits = n + n-1 = 2n -1 = Θ(n)
„ The total cost of quicksort is therefore O(n lg n).
n)
„ Intuitively, a real-life run of quicksort will produce a mix
n Θ(n)
of “bad” and “good” splits
Θ(n − 1) n Θ( n )
‰ Randomly distributed among the recursion tree 1 n-1
‰ Pretend for intuition that they alternate between best-case
(n/2:n/2) and worst-case (n-1:1) (n-1)/2 (n-1)/2 (n-1)/2 (n-1)/2

27 28
Intuition for the Average Case Randomized Quicksort
„ Suppose, we alternate lucky and unlucky cases to „ An algorithm is randomized if its behavior is
d t
determined
i d nott onlyl b
by th
the iinputt b
butt also
l b by values
l
get an average behavior produced by a random-number generator.
L(n) = 2U (n / 2) + Θ(n) lucky
U (n) = L(n − 1) + Θ(n) unlucky „ Exchange A[r] with an element chosen at random
we consequently get from A[p…r] in Partition.
L(n) = 2( L(n / 2 − 1) + Θ(n / 2)) + Θ(n)
= 2 L(n / 2 − 1)) + Θ (n)
„ This ensures that the pivot element is equally likely
to be any of input elements
elements.
= Θ(n log n)

The combination
Th bi ti off goodd andd bad
b d splits
lit would
ld result
lt in
i „ We can sometimes add randomization to an
algorithm in order to obtain good average-case
T(n) = Θ(n lg n), but with slightly larger constant hidden by performance over all inputs.
the Θ-notation.
Θ notation
29 30

Randomized Quicksort Summary: Quicksort

Partition(A,
Randomized-Partition(
Randomized A p p, r) „ In worst-case,, efficiencyy is Θ(n
( 2)
1. i ← Random(p, r) ‰ But easy to avoid the worst-case
2 exchange A[r] ↔ A[i]
2. „ O average, efficiency
On ffi i i Θ(n
is Θ( lg
l n))
3. return Partition(A, p, r)
„ Better space
space-complexity
complexity than mergesort.
mergesort
Randomized-Quicksort(A, p, r)
„ In p
practice, runs fast and widely
y used
1 if p < r
1.
‰ Many ways to tune its performance
2. then q ← Randomized-Partition(A, p, r)
‰ Can be combined effectivelyy
3
3. R d i dQ i k t(A, p, q-1)
Randomized-Quicksort( 1)
4. Randomized-Quicksort(A, q+1, r) „ Various strategies for Partition

31 32