Login | Register

Sorting

Posted on March 1st, 2001
Bruce Eckel's Thinking in Java Contents | Prev | Next 
//: 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.) 

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

IT Offers

Comments

  • There Offer The Discount Daily Necessities Online With High-Quality 0e

    Posted by Robych64 on 03/04/2013 08:10pm

    [p]1956 Norma Armitage, a fencer, was the flag-bearer for America's fourteenth Olympian delegation within the 16th Olympiad at Melbourne, (Australia) . While in the distinctive line of footwear, there are so many different designers and brands which can be vying for the business of clients [url=http://www.airjrodan2013.com/air-jordan-12-retro.html]Jordan 12 Retro[/url] throughout the world . This will encourage the fabric to spread easily and experience the correct quantity of paint . For anyone who is baffled with regards to that which you are thinking about buying find the perfect Christmas gift -- Nike basketball shoes . Such as the situation from a other flight tickets, buying Abu Dhabi Amman Flight Tickets with plenty [url=http://www.2013sportsshoes.com]air jordan on sale[/url] of forethought will give the traveler the benefit of competitive buying, besides watching the schemes the fact that airline companies offer on and again . Individuals continue to spear one another's eyes in the market to enter into Heaven, and attend interfaith peace conferences just like the Parliament with the World's Religions, take note of speakers, sing songs and promise to meet up with again in five years . Contrast it can using the traditional print medium which you could target to a certain extent; although not like performance-based marketing . [url=http://www.airjrodan2013.com/air-jordan-5-retro.html]Jordan 5 Retro[/url] S.[/p][p]Zumba Shoes and Sneakers Zumba has become the hottest fitness craze [url=http://www.2013sportsshoes.com]air jordan for sale[/url] is approximately . Nike Zoom Hyperfuse basketball shoe collection everything culmination to build up this perfect [url=http://www.2013sportsshoes.com]air jordan release dates[/url] shoes . It could possibly go the one thing such as this, "David, I really value how you would [url=http://www.airjrodan2013.com]air jordan retro 4[/url] came inside the residence while i asked and you also even achieved it with out a massive hassle . You can get colors for example a light lavender pink, to your yellow, coffee brown or orange brown . Here are several in the approaches we check my [url=http://www.2013sportsshoes.com/air-jordan-retro-23.html]Jordan Retro 23[/url] creating: I indicate it along with other writers in critique groups . Never consider exactly the price factor when viewing the wholesale websites as they can provide you with the genuine article at very much discounted prices, simply because it appears cheap doesn't imply this can be a knockoff . We may believe for any UGG winter single product, but the perfect interpretation from the star can spot us猫聛陆cheap christian [url=http://www.2013sportsshoes.com]jordan shoes for sale [/url] louboutin seasons . You should check for your option of colored diamonds from any diamond wholesaler.[/p]

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Go Deeper

Most Popular Programming Stories

  • There have been no articles posted today.

More for Developers

Latest Developer Headlines

RSS Feeds