Sorting: Quick Sort
Quick Sort
Divide: Partition the array into two sub-arrays
A[p . . q-1] and A[q+1 . . r] such that each element of
A[p . . q-1] is less than or equal to A[q], which in turn
less than or equal to each element of A[q+1 . . r]
CSE@DIU 2
Quick Sort
Conquer: Sort the two sub-arrays A[p . . q-1] and
A[q+1 . . r] by recursive calls to quick sort.
CSE@DIU 3
Quick Sort
Combine: Since the sub-arrays are sorted in place, no
work is needed to combine them.
CSE@DIU 4
Quick Sort
QUICKSORT(A, p, r)
if p< r
then q 🡨 PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)
CSE@DIU 5
Quick Sort
PARTITION(A, p, r)
x 🡨 A[r]
i 🡨 p-1
CSE@DIU 6
Quick Sort
for j 🡨 p to r-1
do if A[j] <= x
then i 🡨i+1
exchange A[i] 🡨 🡨 A[j]
exchange A[i+1] 🡨 🡨 A[r]
return i+1
CSE@DIU 7
Quick Sort
i p, j r
2 8 7 1 3 5 6 4
(a)
CSE@DIU 8
Quick Sort
p, i j r
2 8 7 1 3 5 6 4
(b)
CSE@DIU 9
Quick Sort
p, i j r
2 8 7 1 3 5 6 4
(c)
CSE@DIU 10
Quick Sort
p, i j r
2 8 7 1 3 5 6 4
(d)
CSE@DIU 11
Quick Sort
p i j r
2 1 7 8 3 5 6 4
(e)
CSE@DIU 12
Quick Sort
p i j r
2 1 3 8 7 5 6 4
(f)
CSE@DIU 13
Quick Sort
p i j r
2 1 3 8 7 5 6 4
(g)
CSE@DIU 14
Quick Sort
p i r
2 1 3 8 7 5 6 4
(h)
CSE@DIU 15
Quick Sort
p i r
2 1 3 4 7 5 6 8
(i)
CSE@DIU 16
Quick Sort
Worst-case partitioning:
The partitioning routine produces one sub-problem
with n-1 elements and another sub-problem with 0
elements. So the partitioning costs θ(n) time.
CSE@DIU 17
Quick Sort
Worst-case partitioning:
The recurrence for the running time
T(n)= T(n-1) + T(0) + θ(n)
=T(n-1) + θ(n)
=----------------- θ(n2)
CSE@DIU 18
Quick Sort
Worst-case partitioning:
The θ(n 2) running time occurs when the input
array is already completely sorted – a common
situation in which insertion sort runs in O(n) time
CSE@DIU 19
Quick Sort
Best-case partitioning:
The partitioning procedure produces two
sub-problems, each of size not more than n/
2.
CSE@DIU 20
Quick Sort
Best-case partitioning:
The recurrence for the running time
T(n) <= 2T(n/2) + θ(n)
= ----- O(n lg n)
CSE@DIU 21
Quick Sort
Best-case partitioning:
The equal balancing of the two sides of the
partition at every level of the recursion
produces faster algorithm.
CSE@DIU 22
Quick Sort
Balanced partitioning:
Suppose, the partitioning algorithm always
produces 9-to-1 proportional split, which
seems quite unbalanced.
CSE@DIU 23
Quick Sort
Balanced partitioning:
The recurrence for the running time
T(n) <= T(9n/10) + T(n/10) +cn
= ------------O(n lg n)
CSE@DIU 24
Quick Sort
Balanced partitioning: The recursion tree
CSE@DIU 25
Quick Sort
Balanced partitioning:
In fact, a 99-to-1 split yields an O(n lg n) running
time. Any split of constant proportionality yields a
recursion tree of depth θ(lg n)
CSE@DIU 26
Quick Sort
Intuition for the average case:
It is unlikely that the partitioning always happens
in the same way at every level.
CSE@DIU 27
Quick Sort
Intuition for the average case:
In the average case, PARTION produces a mix of
“good” and “bad” splits.
CSE@DIU 28
Quick Sort
Intuition for the average case:
The combination of the bad split followed by the good split
produces three arrays of sizes 0, (n-1)/2-1, and (n-1)/2 at a
combined partitioning cost of θ(n) + θ(n-1)= θ(n)
n
Θ(n)
0 n-1
(n-1)/2-1 (n-1)/2
CSE@DIU 29
Quick Sort
Intuition for the average case:
A single level of partitioning produces two sub-arrays of size
(n-1)/2 at a cost of θ(n).
n Θ(n)
(n-1)/2 (n-1)/2
CSE@DIU 30
A Randomized Version of Quick Sort
Instead of always using A[r] as the pivot, we will
use a randomly chosen element from the sub-array
A[p..r].
CSE@DIU 31
A Randomized Version of Quick Sort
Because the pivot element is randomly chosen,
we expect the split of the input array to be
reasonably well balanced on average.
CSE@DIU 32
A Randomized Version of Quick Sort
RANDOMIZED-PARTITION(A, p, r)
i 🡨 RANDOM(p, r)
exchange A[r] 🡨 🡨 A[i]
return PARTITION(A, p, r)
CSE@DIU 33
A Randomized Version of Quick Sort
RANDOMIZED-QUICKSORT(A, p, r)
if p<r then
q 🡨 RANDOMIZED-PARTITION(A, p, r)
RANDOMIZED-QUICKSORT(A, p, q-1)
RANDOMIZED-QUICKSORT(A, q+1, r)
CSE@DIU 34
Textbooks & Web References
• Text Book (Chapter 3)
• [Link]
CSE@DIU 35
Thank you
CSE@DIU 36