Insertion Sort Algorithm
Insertion Sort is one of the simplest, but less effective, sorting algorithms . It works very similar to the way (us humans) sort a hard of playing cards:
| 1. At first none of our cards are sorted . So we start with an “empty” space in our hand were we are going to insert cards one at a time . |
| 2. We take a card from our hand and we put it in the “special place” were we planned to keep our cards sorted . We do this for every card in our initial hand, until we finish them off . |
3. Finding the right position for the insertion is not hard . At this point we can apply two tactics :
|
In our case that “special place” were we are going to insert cards one at a time, is not an additional array, but the array itself . We know for sure that an array of size 1 is always sorted, so we consider that first sorted sub-array, is the block composed by the first element .
For example, we want to sort the following array (with bold, are the elements already sorted):
| 8 | 0 | 3 | 11 | 5 | -1 | 14 | 10 | 1 | 1 | -2 | Array is unsorted . |
| 8 | 0 | 3 | 11 | 5 | -1 | 14 | 10 | 1 | 1 | -2 | The first sorted block is {8} . |
| 0 | 8 | 3 | 11 | 5 | -1 | 14 | 10 | 1 | 1 | -2 | We compare {0} with {8} we move {0} at the new position, we shift {8} . |
| 0 | 3 | 8 | 11 | 5 | -1 | 14 | 10 | 1 | 1 | -2 | We compare {3} with {8}, {0}, we move {3} at the new position, we shift {8} . |
| 0 | 3 | 8 | 11 | 5 | -1 | 14 | 10 | 1 | 1 | -2 | We compare {11} with {8}, {11} remains at the same position . |
| 0 | 3 | 5 | 8 | 11 | -1 | 14 | 10 | 1 | 1 | -2 | We compare {5} with {11}, {8} and {3}, we move {5} at the new position, we shift {8}, {11} . |
| -1 | 0 | 3 | 5 | 8 | 11 | 14 | 10 | 1 | 1 | -2 | We compare {-1} with {11}, {8}, …, {0}, we move {-1} at the new position, we shift {0}, {3}, … {11} . |
| -1 | 0 | 3 | 5 | 8 | 11 | 14 | 10 | 1 | 1 | -2 | We compare {14} with {11}, we move {11} at the new position . |
| -1 | 0 | 3 | 5 | 8 | 10 | 11 | 14 | 1 | 1 | -2 | We compare {10} with {14}, {11}, {8}, we move {10} at the new position, we shift {11}, {14}. |
| -1 | 0 | 1 | 3 | 5 | 8 | 10 | 11 | 14 | 1 | -2 | We compare {1} with {14}, {11}, …, {0}, we move {1} at the new position, we shift {3}, {5}, …, {14} . |
| -1 | 0 | 1 | 1 | 3 | 5 | 8 | 10 | 11 | 14 | -2 | We compare {1} with {14}, {11}, …, {1}, we move {1} at the new position, we shift {3}, {5}, …, {14} . |
| -2 | -1 | 0 | 1 | 1 | 3 | 5 | 8 | 10 | 11 | 14 | We compare {-2} with {14}, {11}, …, {-1}, we move {-2} at the new position, we shift {-1}, {0}, …, {14} . |
The pseudo-code for the algorithm can be easily written as follows:
FUNCTION SORT(A, length) // The array is 0-indexed FOR i:=1 TO length DO key := A[i] j := i - 1 // COMPARE WHILE j >= 0 AND A[j] > key DO // SHIFT A[j+1] := A[j] j := j - 1 // MOVE A[j+1] = key
2. Algorithm Implemenation in Java
The Java implementation of the algorithm is pretty straight-forward (follow the comments):