CS 854 – Advanced Algorithm Analysis
Instructor: Dr. Zuhair Zafar
Lecture# 10: Quick Sort
1
Recap
• Master Method
• Sorting Algorithms
• Incremental Comparison Sorting
• Selection Sort
• Bubble Sort
• Insertion Sort 2
Types of Sorting Algorithms
• Non-recursive/Incremental comparison sorting
• Selection sort
• Bubble sort
• Insertion sort
• Recursive comparison sorting
• Quick sort
• Merge sort
• Heap sort
• Non-comparison linear sorting
• Count sort
• Radix sort
• Bucket sort 3
Recursive Comparison Sorting
There are many ways to design algorithms:
Insertion/Bubble/Selection sort uses an incremental approach
• Having sorted to array A[i..j]
• We insert the single element A[j+1] into its proper place, to get a sorted
array A[i..j+1]
An alternative design approach is “Divide and Conquer”
• Divide the problems into a number of sub-problems
• Conquer the sub-problems by solving them recursively. If sub-problem
sizes are small enough, just solve them in a straight forward manner.
• Combine the solutions to the sub-problems into the solution for the 4
original problem.
Quick Sort
• Quick Sort: orders a list of values by partitioning the list
around one element called a pivot, then sorting each
partition. It is based on divide and conquer approach.
• Key Points: Given an array A to be sorted
• Pick any element x in array A as the pivot (i.e. partition element)
• Partition the remaining elements in A into two groups
• A1 = {all elements in A-{x} that are smaller than x}
• A2 = {all elements in A-{x} that are larger than x}
• apply the quick sort algorithm (recursively) to both partitions
• Trick lies in handling the partitioning 5
• i.e. picking a good pivot is essential to performance
Quick Sort
Pivot
6
Quick Sort
Pivot
7
Quick Sort
Pivot
≤ ¿
8
Quick Sort
Pivot
≤ ¿
9
Quick Sort
Pivot
≤ ¿
≤ ¿ ≤ ¿
10
Quick Sort
11
Quick Sort Example
9 6 5 0 8 2 4 7
12
Quick Sort Example
𝐴 9 6 5 0 8 2 4 7
𝑝 𝑟
13
Quick Sort Example
𝑝𝑖𝑣𝑜𝑡
𝐴 9 6 5 0 8 2 4 7
𝑝 𝑟
14
Quick Sort Example
𝑖 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 9 6 5 0 8 2 4 7
𝑝 𝑟
15
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 9 6 5 0 8 2 4 7
𝑝 𝑟
16
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 9 6 5 0 8 2 4 7
𝑝 𝑟
17
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 9 6 5 0 8 2 4 7
𝑝 𝑟
18
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 9 6 5 0 8 2 4 7
𝑝 𝑟
19
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 9 6 5 0 8 2 4 7
𝑝 𝑟
20
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 9 5 0 8 2 4 7
𝑝 𝑟
21
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 9 5 0 8 2 4 7
𝑝 𝑟
22
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 9 5 0 8 2 4 7
𝑝 𝑟
23
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 9 5 0 8 2 4 7
𝑝 𝑟
24
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 9 0 8 2 4 7
𝑝 𝑟
25
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 9 0 8 2 4 7
𝑝 𝑟
26
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 9 0 8 2 4 7
𝑝 𝑟
27
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 9 0 8 2 4 7
𝑝 𝑟
28
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 0 9 8 2 4 7
𝑝 𝑟
29
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 0 9 8 2 4 7
𝑝 𝑟
30
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 0 9 8 2 4 7
𝑝 𝑟
31
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 0 9 8 2 4 7
𝑝 𝑟
≤ 𝑝𝑖𝑣𝑜𝑡 ¿𝑝𝑖𝑣𝑜𝑡 𝑢𝑛𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑒𝑑
32
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 0 9 8 2 4 7
𝑝 𝑟
33
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 0 9 8 2 4 7
𝑝 𝑟
34
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 0 9 8 2 4 7
𝑝 𝑟
35
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 0 2 8 9 4 7
𝑝 𝑟
36
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 0 2 8 9 4 7
𝑝 𝑟
37
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 0 2 8 9 4 7
𝑝 𝑟
38
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 0 2 8 9 4 7
𝑝 𝑟
39
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 0 2 4 9 8 7
𝑝 𝑟
40
Quick Sort Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝐴 6 5 0 2 4 9 8 7
𝑝 𝑟
41
Quick Sort Example 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝑖 +1 𝑗
𝐴 6 5 0 2 4 9 8 7
𝑝 𝑟
42
Quick Sort Example 𝑝𝑖𝑣𝑜𝑡 , 𝑥=7
𝑖 +1 𝑗
𝐴 6 5 0 2 4 7 8 9
𝑝 𝑟
43
Quick Sort Example
+1
6 5 0 2 4 7 8 9
≤ ¿
44
Quick Sort Example
+1
6 5 0 2 4 7 8 9
≤ ¿
Time complexity of partition algorithm
45
Quick Sort Example
+1
6 5 0 2 4 7 8 9
≤ ¿
Time complexity of partition algorithm
46
Quick Sort Example
+1
6 5 0 2 4 7 8 9
≤ ¿
47
Quick Sort Space Analysis
Best Case Space Complexity
𝑛
𝑛 𝑛
2 2
𝑛 𝑛 𝑛 𝑛
4 4 4 4
.
.
.
48
Quick Sort Space Analysis
Best Case Space Complexity Worst Case Space Complexity
𝑛 𝑛
𝑛
2
𝑛
2 𝑛 −1 0
𝑛
4
𝑛
4
𝑛
4
𝑛
4 𝑛 −2 0
.
.
.
.
.
.
49
Quick Sort Running Time Analysis
Best Case Time Complexity
𝑛
𝑇 (𝑛)
𝑛 𝑛
2 2
𝑂(𝑛) 𝑛 𝑛 𝑛 𝑛
𝑛 4 4 4 4
𝑇( )
2
𝑛
𝑇( )
2
50
Quick Sort Running Time Analysis
Worst Case Time Complexity
𝑛
𝑇 (𝑛)
𝑛 −1 0
𝑂(𝑛) 𝑛 −2 0
𝑇 (𝑛 −1) .
𝑇 (0) .
.
……
51
Quick Sort Average Time Analysis
Assuming that keys are random, uniformly distributed.
• The average case running time occurs when pivot can take any
position at each step
• The size of two sub-arrays will vary at each step
• Say the Partition procedure always splits the array into some
constant ratio b-to-a, e.g. 9-to-1
• What is the recurrence?
52
Picking the Pivot
• How would you pick one?
• Strategy 1: Pick the last element in A
• Works only if input is random
• What if input A is sorted, or even mostly sorted?
• All the remaining elements would go into either A1 or A2!
• Terrible performance!
• Why worry about sorted input?
• Remember Quicksort is recursive, so sub-problems could be sorted
• Plus mostly sorted input is quite frequent
53
Picking the Pivot (contd.)
• Strategy 2: Pick the pivot randomly
• Would usually work well, even for mostly sorted input
• Unless the random number generator is not quite random!
• Plus random number generation is an expensive operation
• Strategy 3: Median-of-three Partitioning
• Ideally, the pivot should be the median of input array A
• Median = element in the middle of the sorted sequence
• Would divide the input into two almost equal partitions
• Unfortunately, harder to calculate median quickly, without sorting
first!
54
• So find the approximate median
• Pivot = median of the left-most, right-most and center elements of array A
• Solves the problem of sorted input
Picking the Pivot (contd.)
• Example: Median-of-three Partitioning
• Let input A = {6, 1, 4, 9, 0, 3, 5, 2, 7, 8}
• Left = 0 and A[left] = 6
• Right = 9 and A[right] = 8
• center = (left + right)/2 = 4 and A[center] =
0
• Pivot
• = Median of A[left], A[right], and A[center]
• = median of 6, 8, and 0 55
• = A[left] = 6
Quick Sort: Not Stable Example
𝐴 4 2 1 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
56
Quick Sort: Not Stable Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 4 2 1 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
57
Quick Sort: Not Stable Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 4 2 1 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
58
Quick Sort: Not Stable Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 4 2 1 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
59
Quick Sort: Not Stable Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 4 2 1 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
60
Quick Sort: Not Stable Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 4 2 1 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
61
Quick Sort: Not Stable Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 2 4 1 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
62
Quick Sort: Not Stable Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 2 4 1 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
63
Quick Sort: Not Stable Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 2 4 1 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
64
Quick Sort: Not Stable Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 2 4 1 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
65
Quick Sort: Not Stable Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 2 1 4 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
66
Quick Sort: Not Stable Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 2 1 4 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
67
Quick Sort: Not Stable Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 2 1 4 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
68
Quick Sort: Not Stable Example
𝑖 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 2 1 4 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
69
Quick Sort: Not Stable Example
𝑖 +1 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 2 1 4 4 3
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
70
Quick Sort: Not Stable Example
𝑖 +1 𝑗 𝑝𝑖𝑣𝑜𝑡 , 𝑥=3
𝐴 2 1 3 4 4
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
71
Quick Sort: Not Stable Example
+1
𝐴 2 1 3 4 4
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
𝐴 1 2 3 4 4
𝑝 𝑟
72
Quick Sort: Not Stable Example
+1
𝐴 2 1 3 4 4
𝑝 𝑟
𝐷𝑢𝑝𝑙𝑖𝑐𝑎𝑡𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑜𝑟𝑑𝑒𝑟
𝑔𝑟𝑒𝑒𝑛
𝑎𝑛𝑑 𝑏𝑙𝑢𝑒
Stable: Duplicate elements should always be in
original order after sorting, i.e., 4 followed by 4
𝐴 1 2 3 4 4 Not Stable
𝑝 𝑟
73
Quick Sort: Final Comments
• What happens when the array contains many duplicate
elements?
• Not stable
• What happens when the size of the array is small?
• For small arrays (N ≤ 50), Insertion sort is faster than quick sort
due to recursive function call overheads of quick sort. Use hybrid
algorithm; quick sort followed by insertion sort when N ≤ 50
• However, Quicksort is usually O(n log2n)
• Constants are so good that it is generally the fastest algorithm known
• Most real-world sorting is done by Quicksort
• For optimum efficiency, the pivot must be chosen carefully
• “Median of three” is a good technique for choosing the pivot
• However, no matter what you do, some bad cases can be
constructed where Quick Sort runs in O(n2) time 74
