Sorting

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

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.

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.

//: 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.

More by Author

Must Read