Insertion sort is also called bubble sort. It iterates the array n times. From left to right, it picks one element during each iteration and "bubbles" it towards the final position.
InsertionSort.java
 |
| bubble sort |
During one iteration, the picked element is compared with its left neighbor. If the left neighbor is larger, they swap. The element continue to compare and swap with the left neighbor until the left neighbor is larger.
0
1
2
3
4
5
6
7
8
9
function InsertionSort(a) {
var N = a.length;
for (var i = 1; i < N; i++){
// Insert a[i] among a[i-1], a[i-2], a[i-3]... ..
for (var j = i; j > 0 && a[j] < a[j-1]; j--) {
exch(a, j, j-1);
}
}
}
Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. As a result, insertion sort requires only a single comparison when the k+1th element is greater than the kth element; while selection sort still have to scan the k elements in order to find the largest or smallest element to swap. The disadvantage of insertion sort is, it has to do a lot of swap on average. For example, when the k+1th element is smaller than the first element, this element need to swap k times in order to swim to the position.
Fun fact:
Flash and EEPROM are the most common bulk storage memories. These memories are generally cheap for read and expensive for write. They will slow down insertion sort, because there are more swaps during the sort. Selection sort, on the other hand, has more read operations but less swap operations, best suit for these cheap memories.
<Prev Next>
