Bruce Eckel's Thinking in Java Contents | Prev | Next

Sorting

One of the things missing in the Java 1.0 and 1.1 libraries is algorithmic operations, even simple sorting. So it makes sense to create a Vector that sorts itself using the classic Quicksort.

A problem with writing generic sorting code is that sorting must perform comparisons based on the actual type of the object. Of course, one approach is to write a different sorting method for every different type, but you should be able to recognize that this does not produce code that is easily re-used for new types.

A primary goal of programming design is to “separate things that change from things that stay the same,” and here, the code that stays the same is the general sort algorithm, but the thing that changes from one use to the next is the way objects are compared. So instead of hard-wiring the comparison code into many different sort routines, the technique of the callback will be used. With a callback, the part of the code that varies from case to case is encapsulated inside its own class, and the part of the code that’s always the same will call back to the code that changes. That way you can make different objects to express different ways of comparison and feed them to the same sorting code.

The following interface describes how to compare two objects, and thus encapsulates “the things that change” for this particular problem: 

//: Compare.java
// Interface for sorting callback:
package c08;

interface Compare {
  boolean lessThan(Object lhs, Object rhs);
  boolean lessThanOrEqual(Object lhs, Object rhs);
} ///:~

For both methods, the lhs represents the “left hand” object and the rhs represents the “right hand” object in the comparison.

A subclass of Vector can be created that implements the Quicksort using Compare. The algorithm, which is known for its speed, will not be explained here. For details, see Practical Algorithms for Programmers , by Binstock & Rex, Addison-Wesley 1995. 

//: SortVector.java
// A generic sorting vector
package c08;
import java.util.*;

public class SortVector extends Vector {
  private Compare compare; // To hold the callback
  public SortVector(Compare comp) {
    compare = comp;
  }
  public void sort() {
    quickSort(0, size() - 1);
  }
  private void quickSort(int left, int right) {
    if(right > left) {
      Object o1 = elementAt(right);
      int i = left - 1;
      int j = right;
      while(true) {
        while(compare.lessThan(
              elementAt(++i), o1))
          ;
        while(j > 0)
          if(compare.lessThanOrEqual(
             elementAt(--j), o1))
            break; // out of while
        if(i >= j) break;
        swap(i, j);
      }
      swap(i , right);
      quickSort(left, i-1);
      quickSort(i+1, right);
    }
  }
  private void swap(int loc1, int loc2) {
    Object tmp = elementAt(loc1);
    setElementAt(elementAt(loc2), loc1);
    setElementAt(tmp, loc2);
  }
} ///:~

You can now see the reason for the term “callback,” since the quickSort( ) method “calls back” to the methods in Compare. You can also see how this technique has produced generic, reusable code.

To use the SortVector, you must create a class that implements Compare for the kind of objects that you’re sorting. This is a place where an inner class is not essential, but it can make sense for code organization. Here’s an example for String objects: 

//: StringSortTest.java
// Testing the generic sorting Vector
package c08;
import java.util.*;

public class StringSortTest {
  static class StringCompare implements Compare {
    public boolean lessThan(Object l, Object r) {
      return ((String)l).toLowerCase().compareTo(
        ((String)r).toLowerCase()) < 0;
    }
    public boolean 
    lessThanOrEqual(Object l, Object r) {
      return ((String)l).toLowerCase().compareTo(
        ((String)r).toLowerCase()) <= 0;
    }
  }
  public static void main(String[] args) {
    SortVector sv = 
      new SortVector(new StringCompare());
    sv.addElement("d");
    sv.addElement("A");
    sv.addElement("C");
    sv.addElement("c");
    sv.addElement("b");
    sv.addElement("B");
    sv.addElement("D");
    sv.addElement("a");
    sv.sort();
    Enumeration e = sv.elements();
    while(e.hasMoreElements())
      System.out.println(e.nextElement());
  }
} ///:~

The inner class is static because it does not need a link to an outer class in order for it to function.

You can see how, once the framework is set up, it’s easy to reuse a design like this – you simply write the class that encapsulates “the things that change” and hand an object to the SortVector.

The comparison forces the strings to lower case, so that the capital A’s end up next to the small a’s and not in some entirely different place. This example shows, however, a slight deficiency in this approach, since the test code above puts the uppercase and lowercase single letters of the same letter in the order that they appear: A a b B c C d D. This is not usually much of a problem, because you’re usually working with longer strings and in that situation the effect doesn’t show up. (The Java 1.2 collections provide sorting functionality that solves this problem.)

Inheritance ( extends) is used here to create a new type of Vector – that is, SortVector is a Vector with some added functionality. The use of inheritance here is powerful but it presents problems. It turns out that some methods are final (described in Chapter 7), so you cannot override them. If you want to create a sorted Vector that accepts and produces only String objects you run into a wall, since addElement( ) and elementAt( ) are final, and these are precisely the methods you’d need to override so they accept and produce only String objects. No luck there.

On the other hand, consider composition: the placing of an object inside a new class. Rather than rewrite the above code to accomplish this, we can simply use a SortVector inside the new class. In this case, the inner class to implement the interface Compare will be created anonymously: 

//: StrSortVector.java
// Automatically sorted Vector that 
// accepts and produces only Strings
package c08;
import java.util.*;

public class StrSortVector {
  private SortVector v = new SortVector(
    // Anonymous inner class:
    new Compare() {
      public boolean 
      lessThan(Object l, Object r) {
        return 
          ((String)l).toLowerCase().compareTo(
          ((String)r).toLowerCase()) < 0;
      }
      public boolean 
      lessThanOrEqual(Object l, Object r) {
        return 
          ((String)l).toLowerCase().compareTo(
          ((String)r).toLowerCase()) <= 0;
      }
    }
  );
  private boolean sorted = false;
  public void addElement(String s) {
    v.addElement(s);
    sorted = false;
  }
  public String elementAt(int index) {
    if(!sorted) {
      v.sort();
      sorted = true;
    }
    return (String)v.elementAt(index);
  }
  public Enumeration elements() {
    if(!sorted) {
      v.sort();
      sorted = true;
    }
    return v.elements();
  }
  // Test it:
  public static void main(String[] args) {
    StrSortVector sv = new StrSortVector();
    sv.addElement("d");
    sv.addElement("A");
    sv.addElement("C");
    sv.addElement("c");
    sv.addElement("b");
    sv.addElement("B");
    sv.addElement("D");
    sv.addElement("a");
    Enumeration e = sv.elements();
    while(e.hasMoreElements())
      System.out.println(e.nextElement());
  }
} ///:~

This quickly reuses the code from SortVector to create the desired functionality. However, not all of the public methods from SortVector and Vector appear in StrSortVector. When reusing code this way, you can make a definition in the new class for each one in the contained class, or you can start with just a few and periodically go back and add more when you need them. Eventually the new class design will settle down.

The advantage to this approach is that it will take only String objects and produce only String objects, and the checking happens at compile time instead of run time. Of course, that’s only true for addElement( ) and elementAt( ); elements( ) still produces an Enumeration that is untyped at compile time. Type checking for the Enumeration and in StrSortVector still happens, of course, it just happens at run-time by throwing exceptions if you do something wrong. It’s a trade-off: do you find out about something for sure at compile time or probably at run-time? (That is, “probably not while you’re testing the code” and “probably when the program user tries something you didn’t test for.”) Given the choices and the hassle, it’s easier to use inheritance and just grit your teeth while casting – again, if parameterized types are ever added to Java, they will solve this problem.

You can see there’s a flag called sorted in this class. You could sort the vector every time addElement( ) is called, and constantly keep it in a sorted state. But usually people add a lot of elements to a Vector before beginning to read it. So sorting after every addElement( ) would be less efficient than waiting until someone wants to read the vector and then sorting it, which is what is done here. The technique of delaying a process until it is absolutely necessary is called lazy evaluation . (There is an analogous technique called lazy initialization which waits until a field value is necessary before initializing it.)

Contents | Prev | Next