Making your Java objects sortable

Making your Java objects sortable: the Comparable interface

In the last post, we looked at how to sort 'naturally' sortable objects in Java such as Strings and Integers. But supposing we've created our own class to represent some arbitrary object or data and want to sort instances of that class? Well, Java can still sort a list of our objects, providing that we tell Java how to order any two instances. For this, we need implement the Comparable interface.

Implementing Comparable

Let's consider an example of a class that represents a playing card in a normal deck of cards. For simplicity, the card will have a suit and a number, both represented by an integer. (In more sophisticated implementations, you might consider using Enums instead of an integers.) When we order our cards, we firstly want them ordered according to suit. We'll define a particular order, namely alphabetical order according to suit name, which in English would be clubs, diamonds, hearts, spades1. Then within a suit, we want the cards ordered numerically.

public class PlayingCard {
  public static final int SUIT_CLUBS    = 1;
  public static final int SUIT_DIAMONDS = 2;
  public static final int SUIT_HEARTS   = 3;
  public static final int SUIT_SPADES   = 4;
  ...

  private int suit;
  private int number;
}

We start by making our class implement the Comparable interface. How exactly this looks depends on whether you're using Java 5 or later (in other words, whether your version of Java supports generics). The generic version looks like this:

public class PlayingCard implements Comparable {
  public int compareTo(PlayingCard o) {
    ...
  }
}

whereas the non-generic (pre Java 5) verion looks like this:

public class PlayingCard implements Comparable {
  public int compareTo(Object o) {
    ...
  }
}

In the non-generic version, we'll have some extra casting to do, but the logic will be essentially the same. We need to make the compareTo() method return an integer that determines the order of two playing cards (this playing card with respect to the one passed in). Now, we look in more detail at implementing the compareTo() method.

Making your Java objects sortable: the compareTo method

We just saw that to make our objects sortable, we need to make them implement the Comparable interface. This means providing a compareTo() method that will define the order of two instances of a given object. Specifically, our compareTo() method needs to return an integer as follows:

a negative number if our object comes before the one passed in;
a positive number if our object comes after the one passed in;
otherwise, zero (meaning they're equal in terms of ordering).
Note that the magnitude of the number doesn't matter. The aim isn't to say "how different" the two objects are, just in which direction. So often, we may as well use -1 and 1 to mean "before" and "after" respectively.

In our example of playing cards, we want to order first by suit and then by number. So we first consider what number we would return just by comparing the suit. If this number is not zero, then we can just return that number: if the suit's different, we don't need to bother comparing the number. So the first part of our comparison looks as follows:

public class PlayingCard implements Comparable {
  public int compareTo(PlayingCard o) {
    if (this.suit < o.suit) {
      return -1;
    } else if (this.suit > o.suit) {
      return 1;
    } else {
      // compare number
    }
  }
}

Now we're left with the cases of cards with an identical suit, in which case we need to compare the number in a similar manner:

public class PlayingCard implements Comparable {
  public int compareTo(PlayingCard o) {
    if (this.suit < o.suit) {
      return -1;
    } else if (this.suit > o.suit) {
      return 1;
    } else {
      // suit is identical: compare number
      if (this.number < o.number) {
        return -1;
      } else if (this.number > o.number) {
        return 1;
      } else {
        return 0;
      }
    }
  }
}

Optimising the compareTo() method

The above implementation of compareTo() will work fine. It has the advantage of being easy to follow. If you write the method this way, you're unlikely to run into trouble.

The method as it stands has the slight disadvantage that it's not very succinct and involves a lot of comparisons. In certain circumstances we can reduce the number of comparisons. On the next page, we'll look at possible optimisations to the compareTo() method. We'll also see that care needs to be taken when applying such optimisations.

Optimising the compareTo method...

We saw an example implementation of the compareTo() method of the Comparable interface. Our implementation was methodical and easy to follow, but a bit "long-winded".

...so long as we're careful!

In some cases we can make the comparison method more succinct, but we need to proceed with caution as we'll see in a second.

Using a subtraction instead of a comparison

The first optimisation that can be made in certain cases is to use a subtraction instead of a comparison of numeric values. In principle, this works thanks to some extremely elementary mathematics:

if a < b, then a - b will be negative; if a > b, then a - b will be positive.
Oh, and of course subtracting a number from itself gives zero. So our card comparison routine can now look as follows:

public class PlayingCard implements Comparable {
  public int compareTo(PlayingCard o) {
    int cardComp = this.suit - o.suit;
    if (cardComp == 0) {
      cardComp = this.number - o.number;
    }
    return cardComp;
  }
}

Using subtraction is a very common idiom for comparing numbers in sorting routines, and is almost certainly the reason why compareTo() is defined to return an integer in the first place. Indeed, you may be wondering why we bothered with the previous version of doing comparisons and returning specific values. Well, it turns out that the subtraction method is incorrect for the general case, although it works here.

Problem with this method: comparing large numbers

The above method works because we know that the numbers we'll be comparing will be small. But ints can only store numbers up to a certain magnitude. So if we know that the difference between the two numbers can exceed about 2 billion (232) we should avoid the above method. Converting to longs gives us extra breathing space (the magnitude can now read 263), but the essential problem remains.

This means, for example, that if you're comparing database keys, you should check very carefully what your database's key allocation policy is if you intend to use this method. (Just because you only have 100,000 keys in your table may not mean that the keys are allocated from that range of numbers.)

Is it worth it?

In tests If you run(on Intel architecture), you will see that:

when the compareTo() involves a single comparison, using a subtraction instead of comparisons makes no appreciable difference;
when two comparisons are involved, using subtraction as above (so that our method has just a single comparison with zero) makes the overall sort about 10% faster.
In other words, in the single-variable case, the "optimisation" appears non-existent and in the two-variable case, the performance benefits are minimal. Possibly the main benefit is therefore a readability issue, at least on modern architecture.

Next...

Next, you may wish to look at how to set an arbitrary sort order using the Java Comparator interface.

Sorting Data with Java Collections

Sorting data with Java Collections: introduction

Here, we will look at how to sort data in Java. To start off with, we'll assume that the problem we have is the following:

we have a List or array of Java objects that is (possibly) out of order;
we want to sort this list or array as a "one-off" action.

By "one-off", we mean that we don't need to keep the list permanently in order as we add and remove elements, though Java does also provide 'permanently sorted' structures if that is what we require. But generally, sorting a list or array can be broken down into two problems:

given any two of the objects that you want to sort (e.g. two Strings if you're sorting a list of string data), how do you determine the correct order of the two elements?;
given the ability to determine the order of two elements, how do you construct a sorting algorithm to sort an entire list of data?
Strictly speaking, these problems aren't totally separate, because some algorithms rely on us being able to measure how far apart two items are. But for sorting in Java, we can generally see the problem in the above two stages. And in fact, for most practical purposes:

Java already provides a good enough solution to the second problem;
for many objects that have an obvious "natural ordering" (e.g. Integers, Floats, Strings), Java also provides a solution to the first problem.
In other words, for the simplest case of sorting a list of Strings or Integers (among other 'simple' objects), Java provides a one-line solution.

Where to go next...

We will look at:

how to sort a list of Strings and other "simple" objects in Java;
how to let Java sort arbitrary objects of your own class, by implementing the Comparable interface;
how to specify your own sort order (whether the objects in question are 'naturally' sortable or not) using Java's Comparator interface.

How to sort a list(a simple object type) of Strings or Integers in Java -

Following on from our introduction to sorting in Java, we consider here one of the simplest cases of sorting a List of simple objects such as Strings or Integers. Let's say we have a simple list of Strings:

List words = new ArrayList(50);
words.add("once");
words.add("upon");
words.add("a");
words.add("time");
...

Now, we can sort this list with a simple call to the following library method:

Collections.sort(words);

The Collections.sort() method will work "out of the can" on lists of various "basic" objects that you'd expect to be able to sort, including instances of Number– the primitive wrapper classes Integer, Long, Float etc plus BigInteger and BigDecimal.

Sorting an array

Sorting an array of these objects is just as easy(Refer point 1 as well at bottom of this post):

Arrays.sort(myArray);

The above method takes an array of objects, but the Arrays class also provides similar methods for sorting primitive arrays.

Next: other issues

What we've seen above is that sorting simple objects in Java such as numbers or strings is generally dead simple. But there are a couple more issues to deal with on the following pages:

What if we want to sort a different type of object, such as one that we've created? For this, we need to look at how to use the Java Comparable interface.
What if we want to control the ordering of a specific type of sort, even if the objects in question are 'naturally sortable'? For example, we might want to perform a case insensitive sort on Strings, or perform a "proper" alphabetic sort that takes account of things like the correct ordering of accents in non-English strings. For this, we need to look at Java Comparators.
In some cases, we may need to consider the performance of the Java sort algorithm: in particular, where we are repeatedly sorting very small lists, a simpler (even if less scalable) algorithm may work better.

Note:

1. In fact, the Collections.sort() method copies the list into an array and calls the Arrays.sort() method before copying the elements back into the list.

Performance of the Java Sorting algorithm -

1. Reading 1
2. Reading 2