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 methodone 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 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 classesthat is, by Integer, Double, Float, Long, and so on (Fig. 9.24). Figure 9.24. Java wrapper classes, such as Integer and Double, implement the Comparable interface. |
public class TestSort { public static int MAXSIZE = 25; public void sort(Comparable[] arr) { Comparable 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 void print(Comparable 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] = new Integer((int) (Math.random() * 10000)); fArr[k] = new 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() } // TestSort class |
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 have defined a sort() method that can sort an array containing any kind of object as long as the object implements the Comparable interface.
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 written and optimized by programming experts. Library sort routines use sort algorithms that are much more efficient than the ones we have discussed.
The java.util.Arrays class contains a polymorphic sort method that is very simple to use. For example, here is how we would use it to sort the two arrays declared in the TestSort program:
java.util.Arrays.sort(iArr); 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-world programmers lots of effort.
Exercise 9.20 | 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. |
Exercise 9.21 | Add a definition of a sort() method that can be added to the definition of the AnalyzeFreq class. Make it so that the array in the class can be sorted into ascending order using the ordering of LetterFreq defined in the preceding exercise. Use the java.util.Arrays.sort() method. |
Exercise 9.22 | Rewrite the main() of the AnalyzeFreq class to make use of the sort() method from the preceding exercise. |