| | |
The insertion sort algorithm relies on the following strategy:
An example is shown below:
5 2 4 1 9 3 7 Notice the very short subarray consisting
* ^ of 5 is (trivially) "in order" and 2 is to
its immediate right
Now we compare 2 with its left neighbor repeatedly,
swapping the two if they are out of order...
5 2 4 1 9 3 7 swap, as 5 > 2
- ^
2 5 4 1 9 3 7 2 moved as far left as it could, so
* * ^ the first 2 elements are now "in order"
and 4 is to their immediate right
Now we compare 4 with its left neighbor repeatedly,
swapping the two if they are out of order...
2 5 4 1 9 3 7 swap, as 5 > 4
- ^
2 4 5 1 9 3 7 do not swap, as 2 < 4
- ^
2 4 5 1 9 3 7 4 moved as far left as it could, so
* * * ^ the first 3 elements are now "in order"
and 1 is to their immediate right.
Now we compare 1 with its left neighbor repeatedly,
swapping the two if they are out of order...
2 4 5 1 9 3 7 swap, as 5 > 1
- ^
2 4 1 5 9 3 7 swap, as 4 > 1
- ^
2 1 4 5 9 3 7 swap, as 2 > 1
- ^
1 2 4 5 9 3 7 1 moved as far left as it could, so
* * * * ^ the first 4 elements are now "in order"
and 9 is to their immediate right.
Now we compare 9 with its left neighbor repeatedly,
swapping the two if they are out of order...
1 2 4 5 9 3 7 do not swap, as 5 < 9
- ^
1 2 4 5 9 3 7 9 moved as far left as it could (it couldn't at all), so
* * * * * ^ the first 5 elements are now "in order"
and 3 is to their immediate right.
Now we compare 3 with its left neighbor repeatedly,
swapping the two if they are out of order...
1 2 4 5 9 3 7 swap, as 9 > 3
- ^
1 2 4 5 3 9 7 swap, as 5 > 3
- ^
1 2 4 3 5 9 7 swap, as 4 > 3
- ^
1 2 3 4 5 9 7 do not swap, as 2 < 3
- ^
1 2 3 4 5 9 7 3 moved as far left as it could, so
* * * * * * ^ the first 6 elements are now "in order"
and 7 is to their immediate right.
Now we compare 7 with its left neighbor repeatedly,
swapping the two if they are out of order...
1 2 3 4 5 9 7 swap, as 9 > 7
- ^
1 2 3 4 5 7 9 do not swap, as 5 < 7
- ^
1 2 3 4 5 7 9 7 moved as far left as it could, so
* * * * * * * all the elements are not "in order".
Given there are not more elements to
the right, we stop.
The implementation of an insertion sort, as shown below, is straight-forward -- especially with the helper methods less() and exch().
public static void insertionSort(Comparable[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
for (int j = i; j > 0; j--) {
if (less(a[j], a[j-1])) {
exch(a, j, j-1);
}
else {
break;
}
}
printOrder(a);
}
}
To analyze the efficiency of this algorithm, we again resort to counting the number of comparisons and exchanges. In the best case, when the list is already in order, note that the algorithm makes $n-1$ comparisons. These are required to verify that each element need not be moved to the left. Of course, if no element moves, there are zero exchanges.
In the worst case (reverse order, with no duplicates), the $2^{nd}$ element must be compared with $1$ element, the $3^{rd}$ element must be compared with $2$ elements, the $4^{th}$ with $3$ elements, the $5^{th}$ with $4$, and so on -- until the last element must be compared with the other $n-1$. Thus there is a total number of comparisons equal to the following:
$$1 + 2 + 3 + \cdots + (n-2) + (n-1) = \frac{n(n-1)}{2} \sim \frac{n^2}{2}$$Thus, the number of comparisons made is $O(n^2)$. Of course -- in the worst case -- every comparison will result in an exchange, so the number of exchanges is also $O(n^2)$.
In the average case, the number of comparisons and exchanges are both smaller (both are $\sim n^2/4$), as elements aren't as far from their final positions as they are when the array is in reverse-order.
Consequently, the insertion sort reduces the number of comparisons from that seen with the selection sort, but at the cost of more exchanges.