Sorting

Bringing Order to the World

Lecture Outline
 Iterative sorting algorithms (comparison based)
 Selection Sort
 Bubble Sort
 Insertion Sort
 Recursive sorting algorithms (comparison based)
 Merge Sort
 Quick Sort

[ CS1020E AY1617S1 Lecture 10 ]

2
Why Study Sorting?
 When an input is sorted, many problems become
easy (e.g. searching, min, max, smallest)

 Sorting has a variety of interesting algorithmic

solutions that embody many ideas
 Comparison vs non-comparison based
 Iterative
 Recursive
 Divide-and-conquer
 Best/worst/average-case bounds
 Randomized algorithms
[ CS1020E AY1617S1 Lecture 10 ]
3
Applications of Sorting
 Uniqueness testing
 Deleting duplicates
 Prioritizing events
 Frequency counting
 Reconstructing the original order
 Set intersection/union
 Finding a target pair x, y such that x+y = z
 Efficient searching

[ CS1020E AY1617S1 Lecture 10 ]

4
Selection Sort
Selection Sort: Idea
 Given an array of n items
1. Find the largest item x, in the range of [0…n−1]
2. Swap x with the (n−1)th item
3. Reduce n by 1 and go to Step 1

[ CS1020E AY1617S1 Lecture 10 ]

6
Selection Sort: Illustration
37 is the largest, swap it with
29 10 14 37 13 the last element, i.e. 13.
Q: How to find the largest?

29 10 14 13 37
x Unsorted items
13 10 14 29 37 Largest item for
x

x Sorted items
13 10 14 29 37

10 13 14 29 37 Sorted!
We can also find the smallest and put it the front instead
[Link]
[ CS1020E AY1617S1 Lecture 10 ]
7
Selection Sort: Implementation
void selectionSort(int a[], int n) {
for (int i = n-1; i >= 1; i--) {
int maxIdx = i; Step 1:
for (int j = 0; j < i; j++) Search for
if (a[j] >= a[maxIdx]) maximum
element
maxIdx = j;
// swap routine is in STL <algorithm>
swap(a[i], a[maxIdx]);
} Step 2:
} Swap
maximum
element
with the last
item i

[ CS1020E AY1617S1 Lecture 10 ]

8
 Selection Sort: Analysis
void selectionSort(int a[], int n) { Number of times
executed
for (int i = n-1; i >= 1; i--) {
int maxIdx = i;  n−1

for (int j = 0; j < i; j++)  n−1

if (a[j] >= a[maxIdx])  (n−1)+(n−2)+…+1

maxIdx = j; = n(n−1)/2
// swap routine is in STL <algorithm>
swap(a[i], a[maxIdx]);  n−1

}
} Total
= c1(n−1) +
• c1 and c2 are cost of statements in c2*n*(n−1)/2
outer and inner blocks = O(n2)

[ CS1020E AY1617S1 Lecture 10 ]

9
Bubble Sort
Bubble Sort: Idea
 Given an array of n items
1. Compare pair of adjacent items
2. Swap if the items are out of order
3. Repeat until the end of array
 The largest item will be at the last position
4. Reduce n by 1 and go to Step 1

 Analogy
 Large item is like “bubble” that floats to the end of the
array

[ CS1020E AY1617S1 Lecture 10 ]

11
Bubble Sort: Illustration

At the end of Pass 2, the second

largest item 29 is at the second
At the end of Pass 1, the largest last position.
item 37 is at the last position.

x
Pair of items
x under comparison
[ CS1020E AY1617S1 Lecture 10 ]
12
Bubble Sort: Implementation
void bubbleSort(int a[], int n) {
for (int i = n-1; i >= 1; i--) { Step 1:
for (int j = 1; j <= i; j++) { Compare
if (a[j-1] > a[j]) adjacent
swap(a[j], a[j-1]); pairs of
numbers
}
}
Step 2:
} Swap if the
items are out
of order

29 10 14 37 13
[Link]

[ CS1020E AY1617S1 Lecture 10 ]

13
Bubble Sort: Analysis
 1 iteration of the inner loop (test and swap) requires
time bounded by a constant c
 Two nested loops
 Outer loop: exactly n iterations
 Inner loop:
 when i=0, (n−1) iterations
 when i=1, (n−2) iterations
 …
 when i=(n−1), 0 iterations
 Total number of iterations = 0+1+…+(n−1) = n(n−1)/2
 Total time = c n(n−1)/2 = O(n2)
[ CS1020E AY1617S1 Lecture 10 ]
14
Bubble Sort: Early Termination
 Bubble Sort is inefficient with a O(n2) time
complexity
 However, it has an interesting property
 Given the following array, how many times will the
inner loop swap a pair of item?

3 6 11 25 39

 Idea
 If we go through the inner loop with no swapping
 the array is sorted
 can stop early!

[ CS1020E AY1617S1 Lecture 10 ]

15
Bubble Sort v2.0: Implementation
void bubbleSort2(int a[], int n) {
for (int i = n-1; i >= 1; i--) { Assume the array
bool is_sorted = true; is sorted before
the inner loop
for (int j = 1; j <= i; j++) {
if (a[j-1] > a[j]) {
swap(a[j], a[j-1]); Any swapping will
invalidate the
is_sorted = false;
assumption
}
} // end of inner loop
if (is_sorted) return; If the flag
} remains true
after the inner
} loop  sorted!

[ CS1020E AY1617S1 Lecture 10 ]

16
Bubble Sort v2.0: Analysis
 Worst-case
 Input is in descending order
 Running time remains the same: O(n2)

 Best-case
 Input is already in ascending order
 The algorithm returns after a single outer iteration
 Running time: O(n)

[ CS1020E AY1617S1 Lecture 10 ]

17
Insertion Sort
Insertion Sort: Idea
 Similar to how most people arrange a hand of
poker cards
 Start with one card in your hand
 Pick the next card and insert it into its proper sorted
order
 Repeat previous step for all cards

1st card: 10♠

2nd card: 5♠

3rd card: K♠

… … … …
[ CS1020E AY1617S1 Lecture 10 ]
19
Insertion Sort: Illustration

Start
x

x
Iteration 1
Unsorted
x To be inserted

Iteration 2 8

Iteration 3

[Link]

[ CS1020E AY1617S1 Lecture 10 ]

20
Insertion Sort: Implementation
void insertionSort(int a[], int n) {
for (int i = 1; i < n; i++) { next is the
item to be
int next = a[i];
inserted
int j;

for (j = i-1; j >= 0 && a[j] > next; j--)

a[j+1] = a[j];
Shift sorted
items to make
a[j+1] = next; place for next
}
} Insert next to
the correct
location

29 10 14 37 13
[Link]
[ CS1020E AY1617S1 Lecture 10 ]
21
Insertion Sort: Analysis
 Outer-loop executes (n−1) times
 Number of times inner-loop is executed depends on
the input
 Best-case: the array is already sorted and
(a[j] > next) is always false
 No shifting of data is necessary
 Worst-case: the array is reversely sorted and
(a[j] > next) is always true
 Insertion always occur at the front

 Therefore, the best-case time is O(n)

 And the worst-case time is O(n2)

[ CS1020E AY1617S1 Lecture 10 ]

22
Merge Sort
Merge Sort: Idea
 Suppose we only know how to merge two sorted
sets of elements into one
 Merge {1, 5, 9} with {2, 11}  {1, 2, 5, 9, 11}
 Question
 Where do we get the two sorted sets in the first place?
 Idea (use merge to sort n items)
 Merge each pair of elements into sets of 2
 Merge each pair of sets of 2 into sets of 4
 Repeat previous step for sets of 4 …
 Final step: merge 2 sets of n/2 elements to obtain a
fully sorted set
[ CS1020E AY1617S1 Lecture 10 ]
24
Divide-and-Conquer Method
 A powerful problem solving technique
 Divide-and-conquer method solves problem in
the following steps
 Divide step
 Divide the large problem into smaller problems
 Recursively solve the smaller problems
 Conquer step
 Combine the results of the smaller problems to produce
the result of the larger problem

[ CS1020E AY1617S1 Lecture 10 ]

25
Divide and Conquer: Merge Sort
 Merge Sort is a divide-and-conquer sorting
algorithm
 Divide step
 Divide the array into two (equal) halves
 Recursively sort the two halves
 Conquer step
 Merge the two halves to form a sorted array

[ CS1020E AY1617S1 Lecture 10 ]

26
 Merge Sort: Illustration
7 2 6 3 8 4 5

Divide into
two halves
7 2 6 3 8 4 5

Recursively
sort the 2 3 6 7 4 5 8
halves

Merge them 2 3 4 5 6 7 8

 Question
 How should we sort the halves in the 2nd step?
[ CS1020E AY1617S1 Lecture 10 ]
27
Merge Sort: Implementation
void mergeSort(int a[], int low, int high) {
if (low < high) {
int mid = (low+high) / 2; Merge sort on
a[low...high]
mergeSort(a, low , mid ); Divide a[ ] into two
mergeSort(a, mid+1, high); halves and recursively
sort them
merge(a, low, mid, high);
}
} Conquer: merge the
Function to merge two sorted halves
a[low…mid] and
a[mid+1…high] into
a[low…high]
 Note
 mergeSort() is a recursive function
 low >= high is the base case, i.e. there is 0 or 1 item
[ CS1020E AY1617S1 Lecture 10 ]
28
 Merge Sort: Example
mergeSort(a[low…mid])
38 16 27 39 12 27
mergeSort(a[mid+1…high])
merge(a[low..mid],
38 16 27 39 12 27 a[mid+1..high])

38 16 27 39 12 27
Divide Phase
Recursive call to
38 16 mergeSort()
39 12

16 38 12 39
Conquer Phase
Merge steps

16 27 38 12 27 39

12 16 27 27 38 39
[Link]
[ CS1020E AY1617S1 Lecture 10 ]
29
Merge Sort: Merge
a[0..2] a[3..5] b[0..5]

2 4 5 3 7 8

2 4 5 3 7 8 2

2 4 5 3 7 8 2 3

2 4 5 3 7 8 2 3 4

24 5 3 7 8 2 3 4 5 Unmerged
x items

2 4 5 3 7 8 2 3 4 5 7 8 x
Items used for
comparison

Merged result in a
x Merged items
Two sorted halves to be
merged temporary array
[ CS1020E AY1617S1 Lecture 10 ]
30
Merge Sort: Merge Implementation
PS: C++ STL <algorithm> has merge subroutine too
void merge(int a[], int low, int mid, int high) {
int n = high-low+1; b is a
int* b = new int[n]; temporary
array to store
int left=low, right=mid+1, bIdx=0; result

while (left <= mid && right <= high) {

if (a[left] <= a[right])
b[bIdx++] = a[left++]; Normal Merging
Where both
else
halves have
b[bIdx++] = a[right++]; unmerged items
}

// continue on next slide

[ CS1020E AY1617S1 Lecture 10 ]
31
Merge Sort: Merge Implementation
// continued from previous slide

while (left <= mid) b[bIdx++] = a[left++];

while (right <= high) b[bIdx++] = a[right++];

for (int k = 0; k < n; k++) Merged result Remaining

are copied items are
a[low+k] = b[k]; copied into
back into a[]
b[]
delete [] b;
}
Remember to free
allocated memory

 Question
 Why do we need a temporary array b[]?
[ CS1020E AY1617S1 Lecture 10 ]
32
Merge Sort: Analysis
 In mergeSort(), the bulk of work is done in the
merge step
 For merge(a, low, mid, high)
 Let total items = k = (high − low + 1)
 Number of comparisons ≤ k − 1
 Number of moves from original array to temporary array = k
 Number of moves from temporary array back to original
array = k
 In total, number of operations ≤ 3k − 1 = O(k)
 The important question is
 How many times is merge() called?

[ CS1020E AY1617S1 Lecture 10 ]

33
 Merge Sort: Analysis
Level 0: Level 0:
mergeSort n items n 1 call to mergeSort

Level 1: Level 1:
mergeSort n/2 items n/2 n/2
2 calls to mergeSort

Level 2: Level 2:
mergeSort n/22 items n/22 n/22 n/22 n/22
22 calls to mergeSort

…
…

…
Level (lg n): Level (lg n):
. . . 2lg n(= n) calls to
mergeSort 1 item 1 1 1 1
mergeSort

n/(2k) = 1  n = 2k  k = lg n

[ CS1020E AY1617S1 Lecture 10 ]

34
Merge Sort: Analysis
 Level 0: 0 call to merge()
 Level 1: 1 calls to merge() with n/2 items in each half,
O(1 x 2 x n/2) = O(n) time
 Level 2: 2 calls to merge() with n/22 items in each half,
O(2 x 2 x n/22) = O(n) time
 Level 3: 22 calls to merge() with n/23 items in each half,
O(22 x 2 x n/23) = O(n) time
 …
 Level (lg n): 2lg(n) − 1(= n/2) calls to merge() with n/2lg(n) (= 1)
item in each half, O(n) time
 Total time complexity = O(n lg(n))
 Optimal comparison-based sorting method
[ CS1020E AY1617S1 Lecture 10 ]
35
Merge Sort: Pros and Cons
 Pros
 The performance is guaranteed, i.e. unaffected by
original ordering of the input
 Suitable for extremely large number of inputs
 Can operate on the input portion by portion

 Cons
 Not easy to implement
 Requires additional storage during merging operation
 O(n) extra memory storage needed

[ CS1020E AY1617S1 Lecture 10 ]

36
Quick Sort
Quick Sort: Idea
 Quick Sort is a divide-and-conquer algorithm
 Divide step
 Choose an item p (known as pivot) and partition the
items of a[i...j] into two parts
 Items that are smaller than p
 Items that are greater than or equal to p
 Recursively sort the two parts
 Conquer step
 Do nothing!

 In comparison, Merge Sort spends most of the time

in conquer step but very little time in divide step

[ CS1020E AY1617S1 Lecture 10 ]

38
Quick Sort: Divide Step Example
Pivot
Choose first
element as pivot 27 38 12 39 27 16
19

Pivot
Partition a[] about
the pivot 27 12 16 27 39 27 38

Pivot
Recursively sort
the two parts 12 16 27 27 38 39

Notice anything special about the

position of pivot in the final
sorted items?
[ CS1020E AY1617S1 Lecture 10 ]
39
Quick Sort: Implementation
void quickSort(int a[], int low, int high) {
if (low < high) { Partition
int pivotIdx = partition(a, low, high) ; a[low...high]
and return the
index of the
quickSort(a, low, pivotIdx-1); pivot item
quickSort(a, pivotIdx+1, high);
Recursively sort
} the two portions
}

 partition() splits a[low...high] into two portions

 a[low ... pivot–1] and a[pivot+1 ... high]
 Pivot item does not participate in any further sorting
[ CS1020E AY1617S1 Lecture 10 ]
40
Quick Sort: Partition Algorithm
 To partition a[i...j], we choose a[i] as the pivot p
 Why choose a[i]? Are there other choices?
 The remaining items (i.e. a[i+1...j]) are divided into 3
regions
 S1 = a[i+1...m] where items < p
 S2 = a[m+1...k-1] where item ≥ p
 Unknown (unprocessed) = a[k...j], where items are yet to be
assigned to S1 or S2

p <p p ?
i m k j
S1 S2 Unknown
[ CS1020E AY1617S1 Lecture 10 ]
41
Quick Sort: Partition Algorithm
 Initially, regions S1 and S2 are empty
 All items excluding p are in the unknown region
 For each item a[k] in the unknown region
 Compare a[k] with p
 If a[k] >= p, put it into S2
 Otherwise, put a[k] into S1

p
i k j
Unknown

[ CS1020E AY1617S1 Lecture 10 ]

42
 Quick Sort: Partition Algorithm
 Case 1: if a[k] >= p

S1 S2
If a[k]=y p, p <p x p y ?
i m k j

S1 S2
Increment k p <p x p y ?
i m k j

[ CS1020E AY1617S1 Lecture 10 ]

43
Quick Sort: Partition Algorithm
 Case 2: if a[k] < p
S1 S2
If a[k]=y < p p <p x p y ?
i m k j
Increment m p <p x p y ?
i m k j

Swap x and y p <p y p x ?

i m k j

Increment k p <p y p x ?
i m k j
[ CS1020E AY1617S1 Lecture 10 ] 44
Quick Sort: Partition Implementation
PS: C++ STL <algorithm> has partition subroutine too
int partition(int a[], int i, int j) {
int p = a[i]; p is the pivot
int m = i; S1 and S2 empty
initially
for (int k = i+1; k <= j; k++) {
Go through each
if (a[k] < p) { element in unknown
m++; Case 2 region
swap(a[k], a[m]);
}
else {
Case 1: Do nothing!
}
}
swap(a[i], a[m]); Swap pivot with a[m]
return m;
} m is the index of pivot

[ CS1020E AY1617S1 Lecture 10 ]

45
Quick Sort: Partition Example

[Link]
[ CS1020E AY1617S1 Lecture 10 ]
46
Quick Sort: Partition Analysis
 There is only a single for-loop
 Number of iterations = number of items, n, in the
unknown region
 n = high − low
 Complexity is O(n)

 Similar to Merge Sort, the complexity is then

dependent on the number of times partition() is
called

[ CS1020E AY1617S1 Lecture 10 ]

47
Quick Sort: Worst Case Analysis
 When the array is already in ascending order

5 18 23 39 44 19
57

empty when m = i

 What is the pivot index returned by partition()?

 What is the effect of swap(a, i, m)?
 S1 is empty, while S2 contains every item except
the pivot
[ CS1020E AY1617S1 Lecture 10 ]
48
Quick Sort: Worst Case Analysis
n

1 n-1

1 n-2 Total no.

of levels
=n
……

As each partition takes

1 1 linear time, the
algorithm in its worst
contains the pivot only! case has n levels and
hence it takes time
n+(n-1)+...+1 = O(n2)
[ CS1020E AY1617S1 Lecture 10 ]
49
Quick Sort: Best/Average Case Analysis
 Best case occurs when partition always splits the
array into two equal halves
 Depth of recursion is log n
 Each level takes n or fewer comparisons, so the time
complexity is O(n log n)
 In practice, worst case is rare, and on the
average we get some good splits and some bad
ones (details in CS3230 :O)
Average time is also O(n log n)

50
Lower Bound: Comparison-Based Sort
 It is known that
 All comparison-based sorting algorithms have a
complexity lower bound of n log n

 Therefore, any comparison-based sorting

algorithm with worst-case complexity
O(n log n) is optimal

[ CS1020E AY1617S1 Lecture 10 ]

51
Radix Sort
Radix Sort: Idea
 Treats each data to be sorted as a character
string
 It is not using comparison, i.e. no comparison
between the data is needed
 In each iteration
 Organize the data into groups according to the next
character in each data
 The groups are then “concatenated” for next iteration

[ CS1020E AY1617S1 Lecture 10 ]

53
Radix Sort: Example

[ CS1020E AY1617S1 Lecture 10 ]

54
Radix Sort: Implementation
void radixSort(vector<int>& v, int d) {
int i;
int power = 1; 10 groups. Each is
queue<int> digitQueue[10]; a queue to retain
the order of item
for (i = 0; i < d; i++) {
distribute(v, digitQueue, power);
collect(digitQueue, v);
power *= 10;
}
}

 distribute(): Organize all items in v into groups using

digit indicated by the power
 collect(): Place items from the groups back into v, i.e.
“concatenate” the groups
[ CS1020E AY1617S1 Lecture 10 ]
55
Radix Sort: Implementation
void distribute(vector<int>& v,
queue<int> digitQ[], int power) {
int digit;
for (int i = 0; i < [Link](); i++){
digit = (v[i]/power) % 10;
digitQ[digit].push(v[i]);
}
}

 Question
 How do we extract the digit used for the current
grouping?

[ CS1020E AY1617S1 Lecture 10 ]

56
Radix Sort: Implementation
void collect(queue<int> digitQ[], vector<int>& v) {
int i = 0, digit;

for (digit = 0; digit < 10; digit++)

while (!digitQ[digit].empty()) {
v[i] = digitQ[digit].front();
digitQ[digit].pop();
i++;
}
}

 Basic Idea
 Start with digitQ[0]
 Place all items into vector v
 Repeat with digitQ[1], digitQ[2], ...
[ CS1020E AY1617S1 Lecture 10 ]
57
Radix Sort: Analysis
 For each iteration
 We go through each item once to place them into
group
 Then go through them again to concatenate the groups
 Complexity is O(n)
 Number of iterations is d, the maximum number
of digits (or maximum number of characters)
 Complexity is thus O(dn)

[ CS1020E AY1617S1 Lecture 10 ]

58