Insertion Sort for Objects
by Charles Kelemen
Under construction. Check back
in a week.
Here is a complete version of insertion sort for ints:
<![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]
toInsert=a[firstuns]; //save value in toInsert,
possPlaceToIns=firstuns; // now a possible place to insert is at firstuns
do
{
possPlaceToIns--; // move the possible insertion place down by
a[possPlaceToIns+1] = a[possPlaceToIns]; // moving object there up
}
while ((possPlaceToIns>0) && (toInsert < a[possPlaceToIns-1]));
a[possPlaceToIns] = toInsert; //found the right spot so put toInsert into it
} //end if
// inv: a[0.. firstuns] is sorted
} //end for
}
]]>
Notice that in the inner do-while loop, sort shifts elements, it does
NOT swap them. Swapping is more costly than simply shifting.
Right now, this sort method is a method in our class SortintTest. We
will first move it out to a Sort class. Since the Sort class might eventually
provide other sorts, we will rename this insertion sort to insort. So the
Sort class (in a file Sort.java) will look like:
<![CDATA[
// by cfk
class Sort {
// Sort a[0 .. (n-1)] into ascending order using insertion sort
static void insort(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]
toInsert=a[firstuns]; //save value in toInsert,
possPlaceToIns=firstuns; // now a possible place to insert is at first
uns
do
{
possPlaceToIns--; // move the possible insertion place down by
a[possPlaceToIns+1] = a[possPlaceToIns]; // moving object there up
}
while ((possPlaceToIns>0) && (toInsert < a[possPlaceToIns-1]));
a[possPlaceToIns] = toInsert; //found the right spot so put toInser
t into it
} //end if
// inv: a[0.. firstuns] is sorted
} //end for
}
}
]]>
Of course, we remove the sort method from our testing program and
invoke the class method insort of Sort by replacing the local
method invocation sort(test, size);
by the class method invocation Sort.insort(test, size);
yielding a test program (in file SortintTest.java) that looks like:
<![CDATA[
// by cfk
import java.io.*;
import java.util.Random;
class SortintTest {
/* 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.insort(test, size);
System.out.println("after sorting");
for (int i = 0; i < size; i++)
System.out.print(" " + test[i]);
System.out.println();
}
}
]]>
It is nice that we now have a separate Sort class, but unfortunately,
as it stands, Sort.insort can only sort arrays of ints. We want
to be able to sort arrays of Objects. That is we would like to have
a method whose signature is:
<![CDATA[
static void insort(Object a[], int n)
]]>
that can sort an array a[] of any kind of Object.
Why can't we simply substitute Object for int
in our successful (for ints) Sort.insort method?
Insertion sort is a 'comparison sort'. There are two places where
insertion sort compares elements to each other to determine
precedence. The first is in the if-statement
if ( a[firstuns] < a[firstuns - 1] ) and the second
is part of the do-while condition
(toInsert < a[possPlaceToIns-1]).
If all objects had a '<' operator, and if that operator
sufficed for all desired orderings, we might be able to pull off the
simple substitution proposed in the paragraph above. But most objects
do NOT have a '<' operator. Furthermore, we may often want to use
different criteria at different times to determine precedence.
There are two ways around this problem. One is to pass to the sort method
a Comparator that provides methods for comparing the Objects in the a[] array.
A second method is to require that each object in the a[] array be responsible
for being able to determine its precedence with respect to any other object
in the a[] array. We will explore the latter technique here.
Java provides a technique to guarantee that a class provides certain
methods. In order to use insort, we will require that each object
in the array to be sorted
supply a 'precedes' method that returns true or false. If robj is
an object and sobj is a
second object robj.precedes(sobj) will return true
if robj should come before sobj. robj.precedes(sobj)
will return false otherwise.
An interface in Java is like a class that provides method signatures
without providing the method bodies. Any class that 'implements'
an interface must provide the bodies for the methods promised by
the interface. The following code in a file called Sortable.java
defines the interface Sortable.
<![CDATA[
// by cfk
public interface Sortable {
public boolean precedes(Object ob);
}
]]>
Here is a small int 'wrapper' class that implements Sortable.
This should be stored in the file MyInts.java:
<![CDATA[
// by cfk
public class MyInts implements Sortable {
private int myval;
public MyInts(int i) {
myval = i;
}
public boolean precedes(Object other) {
return( myval < ( (MyInts) other ).intValue() );
}
public int intValue() {
return myval;
}
public String toString() {
return String.valueOf(myval);
}
}
]]>
Objects of class MyInts can hold a value (myval). They have
a precedes method. Note that we are not checking for errors here.
the precedes method assumes that its argument can be cast to
MyInts. Any object of class MyInts is also an object of 'class'
Sortable.
Do not despair. It may seem like we are going in circles but we are
not. We are well on the way to being able to sort any object that
provides a precedes method.
We can't sort all objects, but we can sort any Sortable objects
(objects that provide a precedes method).
Let us rewrite (for the last time) the Sort.insort method. This time
instead of sorting an array of ints, it will sort an array of
Sortable objects. This should be in the file: Sort.java.
<![CDATA[
//
// by cfk
//
public class Sort
{
//inssort sorts the array a[0..(n-1)] of Sortable objects
//into ascending order by the relation precedes using insertion sort.
public static void inssort(Sortable a[], int n) {
int possPlaceToIns; // index of possible location to insert the
// first unsorted object
Sortable toInsert; // reference to the object to be inserted
for (int firstuns=1; firstuns < n; firstuns++) {
// inv: a[0.. firstuns-1] is sorted
if ( a[firstuns].precedes(a[firstuns - 1]) )
{ //shift some of a [0.. firstuns-1] back to make place for a[firstuns
]
toInsert=a[firstuns]; //save reference to the object in toInsert,
possPlaceToIns=firstuns; // now a possible place to insert is at first
uns
do
{
possPlaceToIns--; // move the possible insertion place down by
a[possPlaceToIns+1] = a[possPlaceToIns]; // moving object there
up
}
while ((possPlaceToIns>0) && (toInsert.precedes(a[possPlaceToIns-1])))
;
a[possPlaceToIns] = toInsert; //found the right spot so put toInser
t into it
} //end if
// inv: a[0.. firstuns] is sorted
} //end for
}
}
]]>
This is almost exactly the same as our old sort for ints.
Let us note the differences.
- The array a[] is now an array of references to Sortable objects.
-
toInsert is a reference to the object to be inserted not the
value of that object.
- We use the precedes method instead of < at two places.
- When we shift elements of the a[] array, we are shifting references
to the objects being sorted; not the values being sorted.
This is a very powerful sort program. We will use it to sort Myints
first because that provides an easy example. We will then move
on to sorting a heterogeneous array of Student, Staff and Faculty
objects. From here on, we will make NO changes to the file Sort.java or
Sortable.java.
Here is a revised testing program to use insort to sort the
Sortable objects of type MyInts. This should be stored in the
file: SortTest.java.
<![CDATA[
// by cfk
import java.io.*;
import java.util.Random;
class SortTest {
/* 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]);
MyInts test[] = new MyInts[size];
Random r = new Random();
for (int i = 0; i < size; i++)
test[i] = new MyInts((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.inssort(test, size);
System.out.println("after sorting");
for (int i = 0; i < size; i++)
System.out.print(" " + test[i]);
System.out.println();
}
}
]]>
This is almost exactly the same as our previous test program except
that now, test[] is an array of MyInts. Since MyInts
implements Sortable, test[] is also an array of Sortable.
You should put the four files ( Sort.java, MyInts.java, SortTest.java,
Sortable.java) in a single directory (or project) and complie and run
SortTest.java. What you should see is the same as our old sorting
of ints. But now we are sorting Sortable objects that just happen
to be ints.
Now make your own class MyDoubles that wrap the primitive type double
and implements Sortable. Change the file SortTest.java to handle
MyDoubles instead of MyInts. Do NOT change the files Sortable.java or
Sort.java. Compile and run your new SortTest.java. Note that
Sort.insort works on this new class without any changes.
Once you understand this thoroughly, you are ready to go on to
sorting a heterogeneous array. Note that when we do this, we
will not change Sort.java at all.