Insertion Sort is as simple and easy to implement as Bubble Sort. Essentially it 'inserts' each key in turn at the correct position within a sored list made up of keys already handled:
public class InsertionSort {
public static void main(String[] args) {
int array[] = {6, 3, 5, 4, 9, 2, 7};
int arraySize = 7;
int i, j, temp;
for (i=1; i < arraySize; i++)
{
temp = array[i];
j = i;
while ((j > 0) && (array[j-1] > temp))
{
array[j] = array[j-1];
j = j - 1;
}
array[j] = temp;
}
for (i = 0; i < arraySize; i++) {
System.out.print(array[i] + " ");
}
}
}
Since keys are repeatedly swapped with their preceding keys until it is in its 'sorted' position, Insertion Sort is least efficient when the list is initially sorted backwards, since the inner for (or while) loop must swap every key to the front of the list. Otherwise, on average it is still more efficient than the Bubble or Selection Sort. Here is an example:
6 3 5 4 9 2 7
3 6 5 4 9 2 7
3 5 6 4 9 2 7
3 5 4 6 9 2 7
3 4 5 6 9 2 7
3 4 5 6 2 9 7
3 4 5 2 6 9 7
3 4 2 5 6 9 7
3 2 4 5 6 9 7
2 3 4 5 6 9 7
2 3 4 5 6 7 9
|
