Unit 22: Sorting
Learning Objectives
After this unit, students should:
 be familiar with four sorting algorithms: counting sort, selection sort, bubble sort, and insertion sort
 be able to implement the above algorithms, argue that they are correct, and analyze their running time
 be aware of the difference between comparisonbased sorting algorithms and counting sort
 be aware of the situations where insertion sort performs better than selection sort and bubble sort.
 be aware of the situations where counting sort performs better than other sorting algorithms.
Sorting
Sorting is one of the most fundamental computational problems. Given a list of items, we want to rearrange the items in some order. We have seen in the previous unit that searching in a sorted list gives us tremendous improvement in efficiency.
In this unit, we assume that the items we wish to rearrange are integers, and we wish to rearrange them in increasing order. We could, however, in practice, sort any type of item.
Counting Sort
The first sorting algorithm we explore today is counting sort. Suppose we are given a list of numbers between a given range, say 0 to \(MAX\). Counting sort works as follows
 scan through the input list once and count how many times each number appears in the list, using an array of size \(MAX+1\) (called the frequency array) to keep track of the frequency of each number.
 scan through the frequency array and put the elements back into the output.
For example, supposed we are asked to sort a list containing only numbers 04: \(\langle 0, 4, 3, 2, 3, 1, 0, 4, 4, 1 \rangle\). Scanning through this list, we count how many times each number appears in the list, and we get the following frequency array: 0 appears twice, 1 appears twice, 2 appears once, 3 appears twice, and 4 appears thrice. So we produce a list of two 0s, two 1s, one 2, two 3s, and three 4s, \(\langle 0, 0, 1, 1, 2, 3, 3, 4, 4, 4\rangle\).
Here is the code that implements the counting sort algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 

Let's consider the running time of the counting sort. We will break it down into three steps of counting sort.
First, initializing freq
array to 0 takes \(O(MAX)\) time.
Second, looping through in
and counting takes \(O(n)\) time (where \(n\) is len
).
What about the third step: populating the output array with sorted numbers? This step involves a double for loop. But, you shouldn't jump to the conclusion that it takes \(O(MAX^2)\) or \(O(n^2)\). Let's analyze this more carefully.
We will go with a more intuitive/informal approach first. What we do here is to store the sorted numbers into the output, there are \(n\) numbers, so it seems reasonable to assume that this step takes \(O(n)\) time.
Let's verify more formally and systematically. The inner loop:
1 2 3 

takes \(O(f_i)\) time, where \(f_i\) is the freq[i]
the number of times \(i\) appears. The outer loop loops through this for different \(i\), from \(i = 0, .. MAX\). So the total number of times is:
This corresponds to the sum of the number of times each number appears in the input, which is simply \(n\). So the third step takes \(O(n)\) time.
The runnning time for counting sort is thus \(O(n + n + MAX)\), which is just \(O(n + MAX)\).
Note that since we do not know the relationship between \(n\) and \(MAX\), we cannot simplify this term to either \(O(n)\) or \(O(MAX)\).
Selection Sort
Another simple sorting algorithm is selection sort. Assuming we are sorting the numbers in increasing order. Given a list of numbers, selection sort partitions the list into two parts, an unsorted part followed by a sorted part. It then repeatedly selects the maximum element from the unsorted part and move it to the front of the sorted part. Here is an example.
Suppose the input is 8 4 23 42 16 15
. At the beginning, the whole list is considered unsorted. We use the 
to indicate the boundary between the sorted and unsorted parts below.
1 

Selection sort selects the largest element from the unsorted part, which is 42, and moves it to the beginning of the sorted part. We get:
1 

Now, the largest element from the unsorted part is 23. Selection sort moves it to the beginning of the sorted part.
1 

This continues until the unsorted part is empty. The list is now sorted.
1 2 3 4 

Here is an implementation of selection sort.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 

To analyze the running time, notice that in the function selection_sort
above, Lines 1718 are repeated \(O(n)\) times. Line 17 calls another function max
. Inside max
, there is another loop that repeats \(j  1\) times. Each time we call max
, j
decreases, so the loop in max
takes one fewer step each time the function is called.
To calculate the total number of steps, we can compute the following sum
\(\sum_{j=1}^{n1}(j1)\), which is just \(0 + 1 + 2 + .. + (n3) + (n2)\)
This sum is the sum of an arithmetic series and equals to \((n2)(n1)/2\). Since we use the BigO notation, we can focus on the term with the highest rate of growth, \(n^2\), and ignore everything else. The running time for selection_sort
function is therefore \(O(n^2)\).
Selection vs Counting Sort
Comparing the running of counting sort \(O(n + MAX)\) vs selection sort \(O(n^2)\), it is clear that counting sort is more efficient  we say that counting sort is a linear time algorithm and selection sort is a quadratic time algorithm.
What is the magic of counting sort? Why don't we just use counting sort all the time, and why bother learning about other sorting algorithms?
It turns out that counting sort is special because it has an assumption that the input numbers fall into a certain range. If \(MAX\) is small, then counting sort is efficient. If \(MAX\) is say, the maximum long values, \(2^{63}1\), then counting sort is not necessarily more efficient (both in terms of time and space) in practice than selection sort.
Because of this assumption, counting sort does not need to compare the inputs during sorting, and thus it can achieve a linear time.
Selection sort, on the other hand, does not assume the range of the input numbers. It is a comparison sort since it compares the input numbers during sorting. It is therefore more general and has a wider range of applications.
We now look at two more comparisonbased sorting algorithms.
Bubble Sort
Bubble sort is probably the most wellknown, underperformed sorting algorithm^{1}, but is taught in most CS classes because of its simplicity. The idea of bubble sort is to make multiple passes through the list. In each pass, we look for all possible adjacent pairs of items. Any adjacent pair that is out of order is swapped so that they are in order. This process repeats until everything is in order.
Let's look at an example. Suppose we have, as an input, the numbers 8 4 23 42 16 15
. In the first pass, we start from the first item and check from left to right. The pair 8 4
is out of order, so we swap them, and we get 4 8 23 42 16 15
. Pairs 8 23
and 23 42
are in order, so we do not need to swap them. The pair 42 16
is out of order. We swap them and get 4 8 23 16 42 15
. The pair 42 15
is again out of order, so we swap them and get 4 8 23 16 15 42
.
The following sequence shows the first pass through the array:
1 2 3 4 5 6 7 8 9 10 11 

After the first pass, notice that the largest element, 42, "bubbles" up through the list until it reaches the maximum position. We can now make the second pass, but we can exclude the last item since it is already in place.
1 2 3 4 5 6 7 8 9 10 

After the second pass, the secondlargest element, 23, is in its position. So we can exclude this item in the subsequent pass.
The rest of the passes operate similarly. In the \(i\)th pass, we scan through array item 0 to \(ni\), swapping any adjacent element that is out of order, until \(i = n  1\), in which case we only have two elements, we swap them if they are out of order, and we are done!
The code for bubble sort can be written as follows:
1 2 3 4 5 6 7 8 9 10 11 12 13 

How many steps does it take to bubblesort an array of \(n\) elements? Since the \(i\)th pass scans through \(ni\) elements, and there are a \(n\) passes in total, the analysis is similar to the one we did for the algorithm to compute the selection sort  bubble sort takes \(O(n^2)\) steps.
Insertion Sort
The next sorting algorithm we are going to discuss is the insertion sort. This is another classic algorithm, that could perform better than bubble sort in some scenarios. Similar to selection sort, we partition the input list into two, a sorted partition, and an unsorted partition. Then we repeatedly take the first element from the unsorted partition, find its rightful place in the sorted partition, and insert it into place. We start with a sorted partition of one element, and we end if the sorted partition contains all the elements.
Take 8 4 23 42 16 15
as an example. We use 
to partition the array into a sorted partition, and an unsorted partition.
1 

We pick the first element on the unsorted partition, 4, and insert it into the sorted partition. This involves shifting the elements in the sorted partition to the right until we find the rightful place for 4
. After this step, the sorted partition grows by 1 and the unsorted partition shrinks by 1.
1 

In the next round, we take 23
, and find its rightful place. It turns out 23
is already in its correct place.
1 

In the next step, 42
is also in its correct place.
1 

16
is the next element, and we insert it between 8 and 23.
1 

Finally, we insert 15
, and we are done, as there is no more element in the unsorted partition.
1 

The code for insertion sort can be written as follows:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 

Animation
Animations for various sorting algorithms, including some of which you will learn in CS2040C, are available online on VisuAlgo.
Problem Set 22
Problem 22.1
In the implementation of bubble sort above, we always make \(n1\) passes through the array. It is, however, possible to stop the whole sorting procedure, when a pass through the array does not lead to any swapping. Modify the code above to achieve this optimization.
Problem 22.2
(a) Suppose the input list to insertion sort is already sorted. What is the running time of insertion sort?
(b) Suppose the input list to insertion sort is inversely sorted. What is the running time of insertion sort?
Problem 22.3
In certain scenarios, a comparison is more expensive than an assignment. For instance, comparing two strings is more expensive than assigning a string to a variable. In this case, we can reduce the number of comparisons during insertion sort by doing the following:
repeat
 take the first element X from the unsorted partition
 use binary search to find the correct position to insert X
 insert X into the right place
until the unsorted partition is empty.
Implement the variation to the insertion sort algorithm above. You may use your solution from Problem 21.1.