1. Overview
As Java developers, we often need to sort elements that are grouped together in a collection. Java allows us to implement various sorting algorithms with any type of data.
For example, we can sort strings in alphabetical order, reverse alphabetical order, or based on length.
In this tutorial, we’ll explore the Comparable interface and its compareTo method, which enables sorting. We’ll look at sorting collections that contain objects from both core and custom classes.
We’ll also mention rules for properly implementing compareTo, as well as a broken pattern that needs to be avoided.
2. The Comparable Interface
The Comparable interface imposes ordering on the objects of each class that implements it.
The compareTo is the only method defined by the Comparable interface. It is often referred to as the natural comparison method.
2.1. Implementing compareTo
The compareTo method compares the current object with the object sent as a parameter.
When implementing it, we need to make sure that the method returns:
- A positive integer, if the current object is greater than the parameter object
- A negative integer, if the current object is less than the parameter object
- Zero, if the current object is equal to the parameter object
In mathematics, we call this a sign or a signum function:
2.2. Example Implementation
Let’s take a look at how the compareTo method is implemented in the core Integer class:
@Override
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
public static int compare (int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}
2.3. The Broken Subtraction Pattern
One might argue that we can use a clever subtraction one-liner instead:
@Override
public int compareTo(BankAccount anotherAccount) {
return this.balance - anotherAccount.balance;
}
Let’s consider an example where we expect a positive account balance to be greater than a negative one:
BankAccount accountOne = new BankAccount(1900000000);
BankAccount accountTwo = new BankAccount(-2000000000);
int comparison = accountOne.compareTo(accountTwo);
assertThat(comparison).isNegative();
However, an integer is not big enough to store the difference, thus giving us the wrong result. Certainly, this pattern is broken due to possible integer overflow and needs to be avoided.
The correct solution is to use comparison instead of subtraction. We may also reuse the correct implementation from the core Integer class:
@Override
public int compareTo(BankAccount anotherAccount) {
return Integer.compare(this.balance, anotherAccount.balance);
}
2.4. Implementation Rules
In order to properly implement the compareTo method, we need to respect the following mathematical rules:
- sgn(x.compareTo(y)) == -sgn(y.compareTo(x))
- (x.compareTo(y) > 0 && y.compareTo(z) > 0) implies x.compareTo(z) > 0
- x.compareTo(y) == 0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z))
It is also strongly recommended, though not required, to keep the compareTo implementation consistent with the equals method implementation:
- x.compareTo(e2) == 0 should have the same boolean value as x.equals(y)
This will ensure that we can safely use objects in sorted sets and sorted maps.
2.5. Consistency with equals
Let’s take a look at what can happen when the compareTo and equals implementations are not consistent.
In our example, the compareTo method is checking goals scored, while the equals method is checking the player name:
@Override
public int compareTo(FootballPlayer anotherPlayer) {
return this.goalsScored - anotherPlayer.goalsScored;
}
@Override
public boolean equals(Object object) {
if (this == object)
return true;
if (object == null || getClass() != object.getClass())
return false;
FootballPlayer player = (FootballPlayer) object;
return name.equals(player.name);
}
This may result in unexpected behavior when using this class in sorted sets or sorted maps:
FootballPlayer messi = new FootballPlayer("Messi", 800);
FootballPlayer ronaldo = new FootballPlayer("Ronaldo", 800);
TreeSet<FootballPlayer> set = new TreeSet<>();
set.add(messi);
set.add(ronaldo);
assertThat(set).hasSize(1);
assertThat(set).doesNotContain(ronaldo);
A sorted set performs all element comparisons using compareTo and not the equals method. Thus, the two players seem equivalent from its perspective, and it will not add the second player.
3. Sorting Collections
The main purpose of the Comparable interface is to enable the natural sorting of elements grouped in collections or arrays.
We can sort all objects that implement Comparable using the Java utility methods Collections.sort or Arrays.sort.
3.1. Core Java Classes
Most core Java classes, like String, Integer, or Double, already implement the Comparable interface.
Thus, sorting them is very simple since we can reuse their existing, natural sorting implementation.
Sorting numbers in their natural order will result in ascending order:
int[] numbers = new int[] {5, 3, 9, 11, 1, 7};
Arrays.sort(numbers);
assertThat(numbers).containsExactly(1, 3, 5, 7, 9, 11);
On the other hand, the natural sorting of strings will result in alphabetical order:
String[] players = new String[] {"ronaldo", "modric", "ramos", "messi"};
Arrays.sort(players);
assertThat(players).containsExactly("messi", "modric", "ramos", "ronaldo");
3.2. Custom Classes
In contrast, for any custom classes to be sortable, we need to manually implement the Comparable interface.
The Java compiler will throw an error if we try to sort a collection of objects that do not implement Comparable.
If we try the same with arrays, it will not fail during compilation. However, it will result in a class cast runtime exception:
HandballPlayer duvnjak = new HandballPlayer("Duvnjak", 197);
HandballPlayer hansen = new HandballPlayer("Hansen", 196);
HandballPlayer[] players = new HandballPlayer[] {duvnjak, hansen};
assertThatExceptionOfType(ClassCastException.class).isThrownBy(() -> Arrays.sort(players));
3.3. TreeMap and TreeSet
TreeMap and TreeSet are two implementations from the Java Collections Framework that assist us with the automatic sorting of their elements.
We may use objects that implement the Comparable interface in a sorted map or as elements in a sorted set.
Let’s look at an example of a custom class that compares players based on the number of goals they have scored:
@Override
public int compareTo(FootballPlayer anotherPlayer) {
return Integer.compare(this.goalsScored, anotherPlayer.goalsScored);
}
In our example, keys are automatically sorted based on criteria defined in the compareTo implementation:
FootballPlayer ronaldo = new FootballPlayer("Ronaldo", 900);
FootballPlayer messi = new FootballPlayer("Messi", 800);
FootballPlayer modric = new FootballPlayer("modric", 100);
Map<FootballPlayer, String> players = new TreeMap<>();
players.put(ronaldo, "forward");
players.put(messi, "forward");
players.put(modric, "midfielder");
assertThat(players.keySet()).containsExactly(modric, messi, ronaldo);
4. The Comparator Alternative
Besides natural sorting, Java also allows us to define a specific ordering logic in a flexible way.
The Comparator interface allows for multiple different comparison strategies detached from the objects we are sorting:
FootballPlayer ronaldo = new FootballPlayer("Ronaldo", 900);
FootballPlayer messi = new FootballPlayer("Messi", 800);
FootballPlayer modric = new FootballPlayer("Modric", 100);
List<FootballPlayer> players = Arrays.asList(ronaldo, messi, modric);
Comparator<FootballPlayer> nameComparator = Comparator.comparing(FootballPlayer::getName);
Collections.sort(players, nameComparator);
assertThat(players).containsExactly(messi, modric, ronaldo);
It is generally also a good choice when we don’t want to or can’t modify the source code of the objects we want to sort.
5. Conclusion
In this article, we looked into how we can use the Comparable interface to define a natural sorting algorithm for our Java classes. We looked at a common broken pattern and defined how to properly implement the compareTo method.
We also explored sorting collections that contain both core and custom classes. Next, we considered the implementation of the compareTo method in classes used in sorted sets and sorted maps.
Finally, we looked at a few use-cases when we should make use of the Comparator interface instead.
As always, the source code is available over on GitHub.