Today we will be discussing various sorting algorithms and examining their efficiency. Sorting is one of the most important operations in computer science, since it is very common to want a collection of data to be in some order. For example, we saw previously that binary search could find an item in a list much faster than sequential search, but only if the list is sorted. When the collection of data that we are sorting is large, it is very important that an efficient algorithm is used, since we would otherwise spend more time than necessary sorting. The algorithms we will discuss can be applied to any type of objects, including integers, floating point numbers, strings, and complex objects.
As long as there is some way to order the objects (the sort key), any type can be sorted. We will assume that the comparison operators (<, >, ==) have been previously defined for whatever type we are working with. We will also assume that we have a function to swap elements of our data type:
template <typename Comparable>
void swap(Comparable &a, Comparable &b)
{
Comparable tmp = a;
a = b;
b = tmp;
}
Selection sort works by finding the item that goes at the end of the list (or the beginning), moving that item to the correct location, and then sorting the rest of the items (either iteratively or recursively). For example, if we start with: 3 2 4 5 1. The first step is to find the largest (5), and swap it with the last element yielding: 3 2 4 1 5. The next step finds the next largest and swaps it with the next to last position: 3 2 1 4 5. This continues until the entire array is sorted. Here is a recursive version:
template <typename Comparable>
void selectionSort(vector<Comparable> &a, int last) {
if (last <= 0) return;
Comparable largest = a[0];
int index = 0;
for (int i = 1; i <= last; i++)
if (a[i] > largest) {
largest = a[i];
index = i;
}
swap(a[index], a[last]);
selectionSort(a, last - 1);
}
If we start with an array containing 3 2 4 5 1, the first function call will move the 5 to the last position, the second will move the 4 to the next-to-last position, and so on.
How long does this take? Sorting algorithms are often evaluated using the number of comparisons that are performed between elements. For each comparison, we never do more than O(1) work. The for-loop is executed n 1 times (each execution does one comparison and sometimes two assignments O(1) total time). Then, we recursively solve a problem we size n 1, so our recurrence relation for the number of comparisons performed is:
T(n) = n 1 + T(n 1)
T(1) = 0
Using iteration, we get:
T(n) = (n 1) + (n 2) + + 1 = n * (n 1) /2 = O(n^2)
This algorithm performs the same number of comparisons in the best, worst, and average case.
In bubble sort (the first sorting algorithm many people learn), comparisons are only performed between adjacent elements in the array. The elements are swapped if they are in the wrong order. Each pass through the data considers each pair of adjacent elements that are unsorted. After the first pass, the largest element must be in the last element of the array, so the next pass only has to consider one less element. Of course, we usually have to perform multiple passes through the data to sort the data completely.
Example: 3 2 4 5 1
We first compare the first two elements (swapping them, since they are out of order):
2 3 4 5 1
We then compare the second and third elements (not swapped), the third and fourth (not swapped) and the fourth and fifth elements (swapped)
2 3 4 1 5
This has bubbled the 5 up to the last position. Since, the array isnt sorted yet, we have to do another pass, but this time we dont have to go as far, since we know the largest element is in the last position. This continues until the array is sorted.
Here is an iterative version of the bubble sort algorithm:
template <typename Comparable>
void bubbleSort(vector<Comparable> &a)
{
bool sorted = false;
// Pass through the data no more than a.size() 1 times
Int pass = 1;
while (pass < a.size()) && (!sorted) {
// Each pass bubbles up the largest item to the top
sorted = true;
for (int index = 0; index < a.size() - pass; index++)
{
if (a[index] > a[index+1])
{
swap(a[index], a[index+1]);
sorted = false;
}
}
pass++;
}
}
Lets look at the running time. In the best case, the data is already sorted. In this case, only one pass through the data is required and this pass performs n 1 comparisons. This is O(n) time. In the worst case, the data is in the completely wrong order. This requires n 1 passes, since the last item can only move one spot during each pass. The first pass requires n 1 comparisons, the second n 2 comparisons and so on, so the worst case is the same as the selection sort: n * (n 1) / 2 = O(n^2) comparisons.
We wont examine the average-case in detail, but this is also O(n^2), if each order of the array elements is equally likely. Note however, that even though they have the same worst-case complexity, bubble sort performs many more swaps than selection sort does. Selection sort performs (at most) n 1 swaps between data elements, while the bubble sort swaps n * (n 1) / 2 elements in the worst case (when the list is sorted in reverse order). If the data elements are very large, this is a significant drawback.
The next algorithm is insertion sort. In this method, the first block of elements is maintained in sorted order and the next unsorted element is inserted into the correct spot at each step. Lets say the list is 3 2 5 4 1. At the beginning, we consider only the first element. This trivial list is sorted, since any list of one element is sorted. Next, we insert the second element at the correct spot. This requires swapping 3 and 2, to get 2 3 5 4 1. Now, we insert the 5 into the sorted elements, but it is already in the correct spot. Next, the 4 gets swapped with the 5, leaving us with 2 3 4 5 1. Finally, the 1 gets inserted, which requires shifting all of the other elements one spot to the right.
Here is code for the algorithm:
template <typename Comparable>
void insertionSort(vector<Comparable> &a)
{
// Sort the next item. After each iteration, items 1..unsorted are sorted.
for (int unsorted = 1; unsorted < a.size(); unsorted++)
{
int loc = unsorted;
Comparable nextItem = a[unsorted];
while (loc > 0 && nextItem < a[loc - 1]) {
a[loc] = a[loc - 1];
loc--;
}
a[loc] = nextItem;
}
}
The outer for-loop (using unsorted) executes n 1 times. The inner for loop (using loc) executes at most unsorted times. So, the total is:
Best case: T(n) = 1 + 1 + + 1 = n 1 = O(n)
Worst case: T(n) = 1 + 2 + + (n 1) = n * (n 1) / 2 = O(n^2)
We can determine the average number of comparisons using the concept of an inversion. In any array, the number of inversions is any pair of numbers that are not the in the correct order (no matter how far apart they are in the array). For our example case: 3 2 4 5 1, there are 5 inversions: (3, 2), (3, 1), (2, 1), (4, 1), (5, 1). Note that each time we move an element in the insertion sort, this fixes exactly one inversion, and we do O(1) work per move. This implies that the work we do is proportional to the number of inversions in the list. There are n (n-1) / 2 pairs of elements in the array. On average, half of them will be inverted if we assume that each ordering is equally likely. So, the average number of inversions is n (n-1) / 4 and, on average, we do O(n^2) work.
This algorithm also moves the data a lot in the worst case, although it does this a little more efficiently than bubble sort does, since it can wait until it gets to the right location before it writes the next unsorted value into the array.
Insertion sort is useful for some cases. One is when you must process the data incrementally. That is, one item is added at a time. For example, in a database application, one record is added at a time. If the records are stored in sorted order, then insertion sort is a good choice. Another case where insertion sort is useful is when the numbers are nearly sorted when you start (bubble sort also works well for this case).
We can prove that if we use an algorithm that only compares and swaps neighbors, the algorithm must be O(n^2) on average. The reason is that we can never fix more than one inversion per swap and we have seen that there are on average O(n^2) of them. We can get around this by using methods that compare and swap elements that are not neighbors.
Carrano 5th edition, Chapter 9:
#8, #9, #10, #12, #15
Carrano 6th edition, Chapter 11:
#2, #3,
#4, #6, #9