Insertion Sort for ints

by Charles Kelemen


Under construction. Check back in a week.

Insertion sort is a well known sorting algorithm. It is an excellent algorithm for short lists or long lists that are 'almost sorted' (for example a list of people sorted by height is 'almost sorted' by weight).

We will start by sorting an array of ints. Later we will generalize our sort to handle a much larger category of objects.

Here is what the method signature will look like:

// Sort a[0 .. (n-1)] into ascending order static void sort(int a[], int n) { } We use the notation a[i .. j] to indicate the sequence of array elements a[i], a[i+1], ... , a[j]. If j<i, this represents an empty sequence. If i=j, this sequence has one element in it.

Suppose the initial array a[0 .. 4] = 24 76 17 72 20
Insertion sort divides the array into a left side which it knows is sorted and a right side of elements that it hasn't considered yet. So initially the left side consists of just
a[0]=24 and the right side is a[1 .. 4] = 76 17 72 20. Here is what happens on this array. firstuns is the index of the first element in the right side of the array (the ordering of which sort is currently ignorant). An asterisk is placed over the array element at firstuns.

------------------------------- * firstuns= 1 * 24 76 17 72 20 a[1] does not precede a[0] so a[0 .. 1] is sorted as is ------------------------------- * firstuns= 2 * 24 76 17 72 20 toInsert = 17 so shift sorted elements right to make place for 17 put 17 into a[0] to get a[0 .. 2] sorted: 17 24 76 72 20 ------------------------------- * firstuns= 3 * 17 24 76 72 20 toInsert = 72 so shift sorted elements right to make place for 72 72 does not precede 24 so put 72 into a[2] to get a[0 .. 3] sorted: 17 24 72 76 20 ------------------------------- * firstuns= 4 * 17 24 72 76 20 toInsert = 20 so shift sorted elements right to make place for 20 20 does not precede 17 so put 20 into a[1] to get a[0 .. 4] sorted: 17 20 24 72 76 after sorting 17 20 24 72 76 In the first pass, firstuns= 1, sort recognizes that 76 does not precede 24 so the sorted left side can be increased without any action.
At the second pass, firstuns= 2, sort recognizes that 17 must be inserted in the left side of the array. In order to accomplish this, 17 is copied into the location toInsert. Because we have a copy of 17 in toInsert, location a[2] is available. We consider this a possible place to insert 17. We call the index of this location possPlaceToIns. sort now shifts possPlaceToIns to the left by shifting array elements to the right. In this pass, the shifting is stopped when we would run off the left end of the array.
At the third pass, firstuns= 3, sort recognizes that 72 must be inserted in the left side of the array. In order to accomplish this, 72 is copied into the location toInsert. Because we have a copy of 72 in toInsert, location a[3] is available. We consider this a possible place to insert 72. We call the index of this location possPlaceToIns. sort now shifts possPlaceToIns to the left by shifting array elements to the right. In this pass, the shifting is stopped when sort realizes that 72 does not precede 24.

Here is a more detailed trace of the behavior of sort on the same elements illustrating the shifting of known sorted array elements to the right and possPlaceToIns to the left.

initial random numbers 24 76 17 72 20 ------------------------------- * firstuns= 1 * 24 76 17 72 20 a[1] does not precede a[0] so a[0 .. 1] is sorted as is ------------------------------- * firstuns= 2 * 24 76 17 72 20 toInsert = 17 so shift sorted elements right to make place for 17 24 76 17 72 20 toInsert = 17 ^ possPlaceToIns = 2 24 76 76 72 20 toInsert = 17 ^ possPlaceToIns= 1 24 24 76 72 20 toInsert = 17 ^ possPlaceToIns= 0 possPlaceToIns==0 so put 17 into a[0] to get a[0 .. 2] sorted: 17 24 76 72 20 ------------------------------- * firstuns= 3 * 17 24 76 72 20 toInsert = 72 so shift sorted elements right to make place for 72 17 24 76 72 20 toInsert = 72 ^ possPlaceToIns = 3 17 24 76 76 20 toInsert = 72 ^ possPlaceToIns= 2 72 does not precede 24 so put 72 into a[2] to get a[0 .. 3] sorted: 17 24 72 76 20 ------------------------------- * firstuns= 4 * 17 24 72 76 20 toInsert = 20 so shift sorted elements right to make place for 20 17 24 72 76 20 toInsert = 20 ^ possPlaceToIns = 4 17 24 72 76 76 toInsert = 20 ^ possPlaceToIns= 3 17 24 72 72 76 toInsert = 20 ^ possPlaceToIns= 2 17 24 24 72 76 toInsert = 20 ^ possPlaceToIns= 1 20 does not precede 17 so put 20 into a[1] to get a[0 .. 4] sorted: 17 20 24 72 76 after sorting 17 20 24 72 76 I am about to give you the skeleton of an insertion sort method. But before that, let's check a testing program. I like to start small and work in very small increments. In order to avoid having to enter a lot of numbers to test our sort, we'll use one of Java's random number generators. Here is some code. import java.io.*; import java.util.Random; class SortintTest { // Sort a[0 .. (n-1)] into ascending order static void sort(int a[], int n) { System.out.println("Gotta write that sort."); } /* Program to test sort */ public static void main(String argv[]) { if (argv.length != 1) { System.out.println("usage: java SortTest array-size"); System.exit(1); } int size = Integer.parseInt(argv[0]); int test[] = new int[size]; Random r = new Random(); for (int i = 0; i < size; i++) test[i] = (int)(r.nextFloat() * 100); System.out.println("initial random numbers"); for (int i = 0; i < size; i++) System.out.print(" " + test[i]); System.out.println(); sort(test, size); System.out.println("after sorting"); for (int i = 0; i < size; i++) System.out.print(" " + test[i]); System.out.println(); } } If you store this in a file called SortintTest.java, compile and run it you should get output like: thyme.cs.swarthmore.edu% javac SortintTest.java thyme.cs.swarthmore.edu% java SortintTest 5 initial random numbers 5 20 71 85 56 Gotta write that sort. after sorting 5 20 71 85 56 thyme.cs.swarthmore.edu% java SortintTest 5 initial random numbers 5 13 98 32 88 Gotta write that sort. after sorting 5 13 98 32 88 thyme.cs.swarthmore.edu%

Of course nothing got sorted because we just stuck in a 'stub' where we need a real sort. But I got my first CS high of the day by writing and debugging a small program. Now to the sort. Here is an outline:

// Sort a[0 .. (n-1)] into ascending order static void sort(int a[], int n) { int possPlaceToIns; // index of possible location to insert the // first unsorted object int toInsert; // the int value to be inserted for (int firstuns=1; firstuns < n; firstuns++) { // inv: a[0.. firstuns-1] is sorted if ( a[firstuns] < a[firstuns - 1] ) { //shift some of a [0.. firstuns-1] back to make place for a[firstuns] } //end if // inv: a[0.. firstuns] is sorted } //end for }

Your task is to write the body of the if statement that does the shifting. This should be done in such a way that the loop invariants are maintained. That is, at the beginning of the body of the for-loop, given the current value of firstuns, a[0.. firstuns-1] is sorted for sure. At the foot of the body of the for-loop, given the current value of firstuns, a[0.. firstuns] is sorted for sure.