Sorting arranges records so that their keys are in nondecreasing order. Before efficient algorithms such as quicksort and heapsort, two simple methods are worth understanding exactly: selection sort and insertion sort. They are the standard examples for loop invariants, for exact operation counts, and for the vocabulary of stability and in-place sorting. The cost analysis uses the model from the unit on complexity growth: we count key comparisons and element moves, and write the result as an exact function of before simplifying it to a growth class.
Definitions
An array is sorted if . A sorting algorithm must output a permutation of its input that is sorted: no element is lost, duplicated or altered. A sort is stable if records with equal keys keep their input order, and in place if it uses only extra cells besides the array.
Definition 3.3.1
(Inversions)
An inversion of is a pair of indices with . Let be the number of inversions. The array is sorted exactly when , and the largest possible value is , attained by a strictly decreasing array.
Selection sort
Selection sort builds the sorted prefix by repeatedly choosing the minimum of the unsorted suffix.
void selection_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int m = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[m]) m = j;
int t = a[i]; a[i] = a[m]; a[m] = t;
}
}
Invariant. Before the pass with index , the prefix holds the smallest elements of the array in sorted order, and every element of is at least as large as each element of the prefix. Initially the prefix is empty. In a pass the inner loop finds a position of a minimum of ; swapping it into position keeps the invariant with the prefix extended by one element. After the pass with the first positions are final and the last element is necessarily the largest, so the array is sorted. The permutation property holds because the only modifications are swaps.
Cost. The inner loop makes comparisons in pass , regardless of the data, so the number of comparisons is exactly
There are at most swaps. Hence selection sort is in comparisons in every case, but uses few moves, which is useful when moving a record is expensive. It is in place. It is not stable: sorting (the letters mark identities) swaps position 0 with position 2 and gives , reversing the equal keys.
Insertion sort
Insertion sort keeps a sorted prefix and inserts the next element into it.
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
Invariant. Before the iteration with index , the prefix is a sorted rearrangement of the original elements . The while loop shifts each element larger than key one place to the right, so when it stops, the gap at lies after all elements not exceeding key and before the larger ones; writing key there makes sorted and contains the same elements. After the whole array is sorted. The loop terminates because decreases and the test guards the left boundary.
Because the shifts use the strict comparison >, an element is never moved past an equal one, so insertion sort is stable. It is also in place.
Theorem 3.3.2
(Shifts equal inversions)
The total number of shifts (executions of a[j + 1] = a[j]) made by insertion sort on equals . The number of key comparisons is at least and at most .
Proof
(Shifts counted by right index)
In iteration , the shifted elements are exactly those in that are strictly greater than , because the prefix is sorted and the loop stops at the first element not exceeding key. Their number is the number of inversions with , that is, the inversions whose right index is . Summing over counts each inversion once. Each iteration makes one comparison per shift, plus at most one more comparison that fails (none if the loop stops at the left boundary), which gives the comparison bound.
Proof X-ray
Where sortedness and the strict test are used
The argument uses the invariant once and the strict inequality once. The invariant, that the prefix is sorted, is what lets a single backward scan decide the whole set : the scan stops at the first element not exceeding the key, and sortedness guarantees that every element further left is not larger either, so no greater element hides behind the stopping point. Without it the claim fails: with the unsorted prefix and key , the scan compares , which is false, and stops with no shift, although is an inversion. The strict test is the second hypothesis. An element equal to the key is not shifted, and an equal pair is not an inversion, so the program and the definition use the same strict inequality. The proof closes by partitioning the inversions according to their right index : each inversion belongs to exactly one iteration, so the per-iteration counts add up to with nothing counted twice.
Consequently the cost is on a sorted array ( comparisons, no shifts) and on a strictly decreasing one ( shifts), and it is in general, which is fast when the input is nearly sorted.
Concept lensCombinatorial
Inversions as adjacent exchanges
Exchange two neighboring entries with . Only the relative order of that one pair changes, so drops by exactly . The sorted array has , hence any method that sorts only by exchanging neighbors needs at least exchanges, and an array with can be sorted with exactly of them. Insertion sort meets this bound: moving the key left past larger elements is equivalent to adjacent exchanges, but it is carried out as shifts and one final write instead of full swaps. The shift count is therefore the number of out-of-order pairs in the input.
Worked examples
Worked example 3.3.3
(Selection sort on [29, 10, 14, 37, 13])
Pass 0: the minimum of the whole array is 10 at index 1; swap it with index 0 to get (4 comparisons). Pass 1: the minimum of is 13 at index 4; swap with index 1: (3 comparisons). Pass 2: the minimum of is 14 at index 2, already in place, so the swap does nothing (2 comparisons). Pass 3: the minimum of is 29 at index 4; swap: (1 comparison). The total is comparisons, with three effective swaps.
Worked example 3.3.4
(Insertion sort on [5, 2, 4, 6, 1, 3])
, key 2: compare with 5 (greater), shift it, then the left boundary stops the loop: (1 comparison, 1 shift). , key 4: 5 is greater, shift; 2 is not greater, stop: (2 comparisons, 1 shift). , key 6: 5 is not greater: no shift (1 comparison). , key 1: compare with 6, 5, 4, 2, all greater, so four shifts and the boundary stops the loop: (4 comparisons, 4 shifts). , key 3: 6, 5, 4 are greater, shifted; 2 is not: (4 comparisons, 3 shifts).
Shifts total . The inversions of are: 5 with 2, 4, 1, 3 (four); 2 with 1 (one); 4 with 1 and 3 (two); 6 with 1 and 3 (two); total , agreeing with the theorem. Comparisons total .
Worked example 3.3.5
(Insertion sort with equal keys and tiny arrays)
Sort , where and are equal keys with distinct identities. For , the key is smaller than , so is shifted and the boundary stops the loop: (1 comparison, 1 shift). For , the key is compared with ; the test is false, so nothing moves (1 comparison, 0 shifts). For , the key is compared with and , both greater, and both are shifted; then is false and the loop stops: (3 comparisons, 2 shifts). The equal keys keep the order , as stability requires.
The inversions of are , and , which is ; the shifts total . The pair is not an inversion because the keys are equal. The comparisons total , between and . For the edge cases and the loop for (i = 1; i < n; ...) does not run: no comparison, no shift, and the array is already sorted.
Subtle points
Common mistake
(Changing the comparison breaks stability)
If the while test in insertion sort is written a[j] >= key, equal elements are shifted past each other. For with and key , the test holds, so is shifted and is written first: . The strict > is what makes the sort stable.
Common mistake
(Fewer swaps does not mean faster)
Selection sort makes at most swaps but always comparisons, so on a sorted input it does far more comparisons than insertion sort. Which is preferable depends on whether a comparison or a move is the dominant cost, and on how disordered the input is.
Counterexample mode
Swapping the minimum into place is not stable
Claim: because selection sort only exchanges elements and never directly exchanges two equal keys, equal keys keep their order. This is false. Run the program above on . In pass the scan sets , finds false, then finds true and sets ; the swap gives . Pass finds false, so it swaps with itself. The output is sorted but has reversed the equal keys. The long-distance swap carried past . The repair is to move the minimum into position by shifting one place to the right instead of swapping, and to choose the leftmost minimum (the strict test a[j] < a[m] already does). On the same input this gives , which is stable, at the price of up to moves per pass and the loss of the at-most--swaps advantage.
Exercises with solutions
Quick check
(1. How many comparisons does selection sort make on 100 elements, and at most how many swaps?)
Solution · Solution 1
Exactly comparisons, whatever the input, and at most swaps, one per pass.
Quick check
(2. Count the inversions of [3,1,4,2] and state the number of shifts insertion sort makes.)
Solution · Solution 2
The inversions are , and , so . Insertion sort makes exactly 3 shifts: key 1 shifts 3 (one shift), key 4 shifts nothing, key 2 shifts 4 and 3 (two shifts).
Quick check
(3. Give the number of comparisons and shifts of insertion sort on [1,2,3,4,5] and on [5,4,3,2,1].)
Solution · Solution 3
On , each of the 4 iterations makes one comparison and no shift: 4 comparisons, 0 shifts. On , iteration shifts all earlier elements and is stopped by the boundary, so it makes comparisons and shifts: comparisons and shifts, which equals .
Quick check
(4. State and prove the invariant that shows selection sort correct.)
Solution · Solution 4
Invariant: before pass , is sorted and each of its elements is at most every element of . For the prefix is empty. In pass , the element is a minimum of , so it is at least the prefix elements and at most all other suffix elements; swapping it to position extends the sorted prefix, and the swapped-out element stays in the suffix, so the condition still holds. At the prefix has elements each at most the single remaining element, so the whole array is sorted.
Quick check
(5. Show by an example that selection sort is not stable and that insertion sort with a non-strict test is not stable.)
Solution · Solution 5
Selection sort on : the minimum 1 is at index 2; swapping with index 0 gives , so the equal keys reversed. Insertion sort with the test a[j] >= key on : key and , so is shifted right and is written at index 0, giving , again reversed.