   |
|
|
|
|
| Insertion sort |
| |
| Insertion sort is an elementary sorting algorithm. It has a time complexity of Θ(n2), thus being slower than heapsort, merge sort and also shellsort. Insertion sort is well suited for sorting small data sets or for the insertion of new elements into a sorted sequence. |
| |
| 5 7 0 3 4 2 6 1 (0) |
| 5 7 0 3 4 2 6 1 (0) |
| 0 5 7 3 4 2 6 1 (2) |
| 0 3 5 7 4 2 6 1 (2) |
| 0 3 4 5 7 2 6 1 (2) |
| 0 2 3 4 5 7 6 1 (4) |
| 0 2 3 4 5 6 7 1 (1) |
| 0 1 2 3 4 5 6 7 (6) |
| |
| Implementation |
| |
| The following simulation illustrates the realization of the algorithm. The corresponding program is given subsequently. |
|
|
| Simulation of insertion sort |
| |
|
|
|
|
| The sorting function is encapsulated in a class InsertionSorter. The method sort passes the array to be sorted to an array a, sets n to its length and calls insertionsort |
| |
| The statement to sort an array b with insertion sort is |
| |
| InsertionSorter.sort(b); |
| |
| The program follows. |
| |
public class InsertionSorter
{
private static int[] a;
private static int n;
public static void sort(int[] a0)
{
a=a0;
n=a.length;
insertionsort();
}
private static void insertionsort()
{
int i, j, t;
for (i=1; i<n; i++)
{
j=i;
t=a[j];
while (j>0 && a[j-1]>t)
{
a[j]=a[j-1];
j--;
}
a[j]=t;
}
}
}
|
