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:
<![CDATA[
// 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.
<![CDATA[
-------------------------------
* 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.
<![CDATA[
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.
<![CDATA[
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:
<![CDATA[
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:
<![CDATA[
// 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.