Object Oriented Design - Polymorphic Sorting

One limitation of the sort routines we built in this guide is that they only work on one particular type of data. If you’ve written an insertion sort to sort ints, you can’t use it to sort doubles. What would be far more desirable is a polymorphic sort method: one method that could sort any kind of data. This is easily done by making use of Java wrapper classes, such as Integer and Double, together with the java.lang.Comparable interface, which is specially designed for this purpose.

The java.lang.Comparable interface consists of the method:

public abstract interface Comparable {
  public int compareTo(Object o);// Abstract method
}

By implementing compareTo(), a class can impose an order on its objects. The Comparable interface is implemented by all of Java’s wrapper classes—that is, by Integer, Double, Float, Long, and so on.

The compareTo() method takes an Object parameter and returns an int. It is meant to be invoked as o1.compareTo(o2), where o1 and o2 are objects of the same type. Classes that implement compareTo() must abide by the following rules for its return value:

if (o1 < o2)       then o1.compareTo(o2) < 0
if (o1.equals(o2)) then o1.compareTo(o2) == 0
if (o1 > o2)       then o1.compareTo(o2) > 0

In other words, if o1 < o2, then o1.compareTo(o2) will return a negative integer. If o1 > o2, then o1.compareTo(o2) will return a positive integer. And if o1 and o2 are equal, then o1.compareTo(o2) will return 0.

For a class that implements Comparable, we can use the method to help sort its elements. For example, the following revised version of insertionSort() method can be used to sort any array of Comparable objects—that is, any array of objects whose class implements Comparable:

public void sort(Comparable[] arr) {
  Comparable temp;   // Temporary variable for insertion
  for (int k = 1; k < arr.length; k++)  {
    temp = arr[k];    // Remove it from array
    int i;
    for (i = k-1; i >= 0 && arr[i].compareTo(temp) > 0; i--) 
      arr[i+1] = arr[i];   // Move it right by one
    arr[i+1] = temp;        // Insert the element
  }
} // sort()

In this version, the parameter is an array of Comparable. Thus, we can pass it any array whose elements implement Comparable, including an array of Integer or Float, and so on. Then, to compare elements of a Comparable array, we use the compareTo() method:

for (i = k-1; i >= 0 && arr[i].compareTo(temp) > 0; i--) 

Note that our algorithm no longer refers to ints, as in the original insertion sort. Indeed, it doesn’t mention the specific type, Integer, Float, or whatever, of the objects that it is sorting. It refers only to Comparables. Therefore, we can use this method to sort any type of object, as long as the object’s class implements the Comparable interface. Thus, by using Comparable, we have a more general insertionSort() method, one that can sort any one-dimensional array of Comparables.

This example of polymorphic sorting illustrates once again the great power of inheritance and polymorphism in object-oriented programming. The Integer and Float classes use class inheritance to inherit features from the Object class, and they use interface implementation to inherit the compareTo() method from the Comparable class. By implementing versions of the toString() and compareTo() methods that are appropriate for these wrapper classes, Java makes it easier to use Integer and Float objects in a variety of contexts. Taken together, inheritance and polymorphism enable us to design very general and extensible algorithms. In this example, we defined a sort() method that can sort an array containing any kind of object as long as the object implements the Comparable interface.

The java.util.Arrays.sort() Method

While sorting algorithms provide a good way to introduce the concepts of array processing, real-world programmers never write their own sort algorithms. Instead they use library methods, which have been written and optimized by programming experts. Moreover, library sort routines use sort algorithms that are much more efficient than the ones we’ve discussed.

The java.util.Arrays class contains a polymorphic sort method that is very simple to use. For example, here’s how we would use it to sort the two arrays:

java.util.Arrays.sort(iArr);
java.util.Arrays.sort(fArr);