OBJECT-ORIENTED DESIGN: Polymorphic Sorting (Optional)

Section 9.9 OBJECT-ORIENTED DESIGN: Polymorphic Sorting (Optional)

One limitation of the sort routines developed so far 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—that is, 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.

Subsection 9.9.1 The `Comparable` Interface

The java.lang.Comparable interface consists of the compareTo() 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 (Fig. 9.24).

Figure 9.9.1. : Java wrapper classes, such as `Integer` and `Float`, implement the Comparable interface.

As we saw in Chapter 8, Java interfaces allow us to create a form of multiple inheritance. For example, as Figure 9.9.1 shows, an Integer is both an Object and a Comparable. One implication of this is that an Integer can be used in any method that takes either an Object parameter or a Comparable parameter.

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.

Subsection 9.9.2 Sorting Comparables

For a class that implements Comparable, we can use the compareTo() 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 for any type T.

  public  <T extends Comparable<T>> void sort(T[] arr) {
    T 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 any Object type T. Thus, we can pass it 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 Comparable s. 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 Comparable s.

The TestSort class (Figure 9.9.2 and Listing 9.9.3) provides an example of how to use the polymorphic sort() method.

It contains three methods: The sort() method that we just described; a polymorphic print() method, which can be used to print the values of any array of Comparable; and a main() method. The main() method creates arrays of Integer and Float and then uses the polymorphic sort() method to sort them. Note how the print() method uses the polymorphic toString() method to print the elements of a Comparable array.

public class TestSort {
  public static int MAXSIZE = 25;

public  <T extends Comparable<T>> void sort(T[] arr) {
    T temp;      // Temporary variable for insertion

for (int k = 1; k < arr.length; k++) { // For each element
      temp = arr[k];                     // Remove it
      int i;
      for (i = k-1; i >= 0 && arr[i].compareTo(temp) > 0; i--)
        arr[i+1] = arr[i]; // Move larger to the right
      arr[i+1] = temp;       // Insert the element
    }
  } // sort()
  
  public  <T extends Comparable<T>> void print(T[] arr) 
  {
    for (int k = 0; k < arr.length; k++) {
      if (k % 5 == 0)  
         System.out.println();  // New row
      System.out.print(arr[k].toString() + "\t");
    }
    System.out.println();
  }
  
  // Sorts two different types of array with the same method.
  public static void main(String args[]) {
    Integer iArr[] = new Integer[TestSort.MAXSIZE];
    Float fArr[] = new Float[TestSort.MAXSIZE];
    for (int k = 0; k < TestSort.MAXSIZE; k++) { // Create data
      iArr[k] = ((int) (Math.random() * 10000));
      fArr[k] = ((float) Math.random() * 10000);
    }
    TestSort test = new TestSort();
    test.sort(iArr);     // Sort and print Integers
    test.print(iArr);
    test.sort(fArr);     // Sort and print Floats
    test.print(fArr);
  } // main()
}

Listing 9.9.3. TestSort uses the polymorphic sort() method to sort either Integers or Floats.

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.

Subsection 9.9.3 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 declared in the TestSort program:

java.util.Arrays.sort(iArr);
// or if you: import java.util.*;
Arrays.sort(fArr);

That’s all there is to it! Obviously, learning how to use Java’s class and method library, saves real-word programmers lots of effort. Try it below!

Activity 9.9.1.

Run the code below a couple times to populate the array with random numbers and see the result of the Arrays.sort() method.

Exercises Self-Study Exercises

1. Polymorphic Sort.

This exercise has three parts:

Add a definition of a compareTo() method to the LetterFreq class so that it implements the Comparable interface. The method should define one object to be less than another object if its freq instance variable is less.
Add a definition of a sort() method that can be added to the definition of the AnalyzeFreq class. Make it so the array in the class can be sorted into ascending order using the ordering of LetterFreq defined in the previous exercise. Use the java.util.Arrays.sort() method.
Rewrite the main() of the AnalyzeFreq class to make use of the sort() method of the previous exercise.

public class AnalyzeFreq {
    
      private LetterFreq[] freqArr; //An array of frequencies
      
      public AnalyzeFreq() {
        freqArr = new LetterFreq[26];
        for (int k = 0; k < 26; k++) {
          freqArr[k] = new LetterFreq((char)('A' + k), 0);
        } //for
      }
      public void countLetters(String str) {
        char let; //For use in the loop.
        str = str.toUpperCase();
        for (int k = 0; k < str.length(); k++) {
          let = str.charAt(k);
          if ((let >= 'A') && (let <= 'Z')) {
            freqArr[let - 'A'].incrFreq();
          } //if
        } //for
      }
      public void printArray() {
        for (int k = 0; k < 26; k++) {
          System.out.print("letter: " + freqArr[k].getLetter());
          System.out.println(" freq: " + freqArr[k].getFreq());
        } //for
      } 
  
  public static void main(String[] argv) {
    AnalyzeFreq af = new AnalyzeFreq();
    af.countLetters("Now is the time for all good students" +
      " to study computer related topics.");
    af.printArray();
  } //main()
} //AnalyzeFreq

class LetterFreq {
  private char letter;    //A character being counted
  private int freq;       //The frequency of letter
  public LetterFreq(char ch, int fre) {
      letter = ch;
      freq = fre;
  }
  public char getLetter() {
      return  letter;
  }
  public int getFreq() {
      return  freq;
  }
  public void incrFreq() {
      freq++;
  }
} //LetterFreq

You have attempted of activities on this page.

Prev Top Next