trypots.nethomeInsertion Sort
Insertion sort is likened to sorting a hand of playing cards. Many individuals, when sorting a hand of cards, will start on one side, put the first card in place, and then move methodically from left to right inserting other cards where they belong. In this way, your hand becomes increasingly sorted as you go, until ultimately the entire hand is sorted. Insertion sort also begins by starting out with the first element, treating it as a one element sorted subarray, and continuing methodically through the rest of the array. However, unlike a card player, the insertion algorithm doesn't know at a glance where an element belongs. So there are many repeated sweeps through array element while the algorithm finds the right place for elements, especially as the subarray grows in size and if an element must be moved far from its original position. So the performance is generally not good for large arrays. For an interesting solution to this problem, see Shellsort.
Nevertheless, insertion sort is easy to write and is fast on small arrays. It also performs extremely well on arrays that are partially or mostly sorted. In such cases insertion sort can be the sort algorithm of choice. Finally, insertion sort is stable, meaning that it will not interfere with a previous sort using a different basis of comparison. For example, if you have sorted by first name, and then you sort by last name, the first name sorting remains intact. The result would be an ordering by last name, then first name. Many sort algorithms do not have this property.
Here we present two implementations, a basic insertion sort algorithm, followed by an insertion sort algorithm with a "tweak" to improve performance. In the first example, without a (j > 0) in the inner loop, the sort may run past the beginning of the array, which would be a serious bug. In InsertionWithSentinel, we force the first element to be the smallest, which acts as a guard so that the loop always terminates when it reaches the beginning of the array. This tweak is a good example of a small change that could effect peformance if many repeated calls are made to a function. However, I don't recommend the tweaked version of insertion sort since it can have a small effect on the behavior of the algorithm (see Insertion Sort Stability). The example given in the link is not entirely convincing since the changes demonstrated arise only in a hand of cards not properly sorted to begin with (there is no rule about the ordering of suits). Nevertheless, it's enough to provoke caution. And in any case, insertion sort is not at all appropriate for large data sets and such tweaks are missing forests for trees. So proceed with caution but do enjoy this basic algorithm and know its virtues (simplicity, stability, and, under certain circumstances, usefulness).
Insertion Sort:
public class Insertion {
public static void sort(int[] a) {
int i = 0;
int j = 0;
int temp = 0;
for(i = 1; i < a.length; i++) {
temp = a[i];
j = i;
while((j > 0) && (temp < a[j-1])) {
a[j] = a[j-1];
j--;
}
a[j] = temp;
}
}
}
Insertion Sort (with sentinel):
public class InsertionWithSentinel {
public static void sort(int[] a) {
int i = 0;
int j = 0;
int temp = 0;
int N = a.length;
//First find minimum value
for(i = 1; i < N; i++) {
if(a[i] < a[i-1]) {
j = i;
}
}
temp = a[0];
a[0] = a[j];
a[j] = temp;
//Insertion sort with sentinel
for(i = 1; i < N; i++) {
temp = a[i];
j = i;
while(j > 0 && temp < a[j-1]) {
a[j] = a[j-1];
j--;
}
a[j] = temp;
}
}
}
Client example:
import java.util.Random;
public class Test1 {
public static void main(String[] args) {
int size = 0;
//User may use a command line argument for testing larger arrays
if(args.length < 1) {
size = 24;
}
else {
size = Integer.parseInt(args[0]);
}
//array of randomly created ints
for(int count = 0; count < 2; count++) {
Random random = new Random(42);
int[] a = new int[size];
for(int i = 0; i < a.length; i++) {
a[i] = random.nextInt(1000);
}
//print unsorted array, if not too large
if(count == 0 && a.length < 50001) {
System.out.println("Unsorted:");
print(a);
}
if(count == 0) {
Insertion.sort(a);
}
else {
InsertionWithSentinel.sort(a);
}
//validate sort
if(!(isSorted(a))) {
System.out.println("Error: sort failed.");
}
//print sorted array, if not too large
else if(a.length < 50001) {
System.out.println("Sorted" +
(count == 1 ? " (with sentinel)" : "") + ":");
print(a);
}
//for a large array just report success or failure.
else {
System.out.println("Sort" +
(count == 1 ? " (with sentinel)" : "") + " succeeded.");
}
}
}
public static boolean isSorted(int[] a) {
for(int i = 1; i < a.length; i++) {
if(a[i] < a[i-1]) {
return false;
}
}
return true;
}
public static void print(int[] a) {
int i = 0;
if(a.length <= 8) {
for(i = 0; i < a.length; i++) {
System.out.printf("" + a[i]);
}
}
else if(a.length < 50001) {
for(i = 1; i < a.length; i++) {
if((i % 8) == 0) {
System.out.printf(" %5d%n", a[i-1]);
}
else {
System.out.printf(" %5d", a[i-1]);
}
}
System.out.printf(" %5d\n\n", a[i-1]);
}
}
}