Sorting a Collection

One of the drawbacks of Vector when it was first introduced was that it provided no way to sort its elements. You were left to either write your own sort routines or incorporate a set of third-party classes to provide what is typically a key function in most applications. Fortunately, the collections framework addressed the issue of sorting directly and provided the functionality as part of the API.

The Comparable Interface

Throughout this chapter, classes have been discussed that make use of the natural ordering of objects. A class has a natural ordering when it implements the java.lang.Comparable interface:

 public interface Comparable {   public int compareTo(Object o); } 

The compareTo method of this interface is implemented by a class to compare the current object with the object passed in as a parameter for order. The method returns a positive integer if the Object argument is less than the current object, zero if they are equal, or a negative integer if the argument is greater. You should implement this interface for any class you write whose instances can be sorted or ordered. The ordering produced by this interface is referred to as natural because it is the order decided internally by the class without any knowledge of how it might be used.

Many of the core API classes implement Comparable to simplify the display of their instances. This list of classes includes, among others, Character, File, Long, Short, String, Float, Integer, Byte, Double, BigInteger, BigDecimal, and Date.

The Comparator Interface

You might also find it necessary to sort objects that do not have a natural ordering, or to impose a different sorting algorithm on a class that does. The Comparator interface allows you to sort a collection regardless of its natural ordering. This interface declares two methods , of which compare is the more important:

 public interface Comparator {   public int compare(Object o1, Object o2);   public boolean equals(Object obj); } 

The compare method of Comparator accepts two Object arguments and returns an integer value that defines their sort order. This return value must be a negative value if the first object is less than the second, a zero if they are equal, or a positive value if the first object is greater. Normally, you will allow the Object implementation of equals to satisfy the remainder of the interface. The only reason to override equals would be if a particular implementation could improve performance in cases where the method gets called often.

Tip

Although not required, you should declare any comparators you write to implement java.io.Serializable. If you assign a Comparator to a TreeMap or TreeSet, it must be Serializable to allow its associated container to be serialized.

The preceding section listed String as an example of a Comparable class. Java's natural ordering for String is case sensitive, which might not always be desirable. If you want to sort a collection of strings and ignore case, the String class holds a class field named CASE_INSENSITVE _ORDER that is a case-insensitive implementation of Comparator. This is one case where the usefulness of being able to override the natural ordering of a class is easy to see.

Using Collections.sort()

The Collections class in the java.util package consists solely of static utility methods that simplify working with collection classes. Included among these are two sorting operations for lists:

 public static void sort(List list) public static void sort(List list, Comparator c) 

The single-argument version sorts a List based on the natural ordering of its elements, and the other uses a specified Comparator. You can apply these methods to any List that is modifiable as long as its elements are mutually comparable. This means that the compareTo, or compare, method must not throw a ClassCastException when attempting to compare any two elements.

The Collections class also provides another interesting method related to sorting:

 public static Comparator reverseOrder() 

The reverseOrder method returns a Comparator that sorts a collection of objects that implement Comparable in the reverse of its natural ordering. If you want to sort a group of Integer or String instances in reverse order, this method, combined with the sort method of Collections that accepts a Comparator, provides a simple and efficient way to do it.

Listing 10.4 shows an example of sorting a class that implements Comparable using its natural ordering, and using a Comparator.

Listing 10.4 AuctionBid.java ”Comparable and Comparator Sorting

 import java.util.*; import java.text.NumberFormat; public class AuctionBid implements Comparable {   // class holds the bidder's name and the amount bid   String bidder;   int amount;   public AuctionBid(String name, int bid) {     bidder = name;     amount = bid;   }   public String toString() {     // get a currency formatter to make the output look nice     NumberFormat formatter = NumberFormat.getCurrencyInstance();     return bidder + " bid " + formatter.format(amount);   }   // implement Comparable interface   public int compareTo( Object other ) {     // this method defines the natural ordering of     // the class to be based on ascending bid amount     AuctionBid otherBid = (AuctionBid)other;     if ( otherBid == null ) {       return 1;     }     if ( this.equals(otherBid)  (amount == otherBid.amount) ) {       return 0;     }     return ( otherBid.amount < amount ) ? 1 : -1;   }   // define a Comparator that instead sorts on the bidder's name   static class BidComparator implements Comparator, java.io.Serializable {     public int compare(Object o1, Object o2) {       AuctionBid firstBid = (AuctionBid)o1;       AuctionBid secondBid = (AuctionBid)o2;       if ( (firstBid == null)  (firstBid.bidder == null) ) {         return ((secondBid == null)  (secondBid.bidder == null)) ? 0 : -1;       }       if ( (secondBid == null)  (secondBid.bidder == null) ) {         return 1;       }       // String implements Comparable, so let it do the work       return firstBid.bidder.compareTo(secondBid.bidder);     }   }   public static void main( String args[] ) {     // fill a list with 5 bids     ArrayList bidList = new ArrayList();     for ( int i=0; i<5; i++ ) {       // generate a random number 0-100 for a bid amount       bidList.add( new AuctionBid("Bidder" + i, (int)(Math.random()*100)) );     }     // sort the bids in natural order and display them     Collections.sort( bidList );     System.out.println("Natural order sort by bid amount");     System.out.println( bidList );     // impose a different sort using a Comparator     Collections.sort( bidList, new BidComparator() );     System.out.println("Comparator sort by bidder name");     System.out.println( bidList );   } } 

The code in Listing 10.4 generates random numbers for bids, but, if you execute it, you'll get output similar to the following:

 Natural order sort by bid amount [Bidder1 bid .00, Bidder2 bid .00, Bidder3 bid .00, Bidder4 bid .00, Bidder0 bid .00] Comparator sort by bidder name [Bidder0 bid .00, Bidder1 bid .00, Bidder2 bid .00, Bidder3 bid .00, Bidder4 bid .00]