The Java Sorting Conundrum: Comparable vs Comparator Interfaces
By
Introduction
In this article I demonstrate how to implement the Comparable and Comparator interfaces in Java. Both of these interfaces are used to control the order in which objects in Collections and Arrays are sorted. I additionally discuss when you might want to use one over the other depending on use cases.
The code to used in the is article including the JavaFX sorting animation application is hosted on GitHub for you to view and experiment with.
Comparable<T> Interface
The Comparable<T> interface is described in the Oracle Java Docs as being used to impose a natural ordering accomplished through the implementation of the Comparable interface's compareTo(T) method. The Comparable interface is defined as shown below.
public interface Comparable<T> {
public int compareTo(T o);
}When implementing the compareTo method you are comparing the class instance within the current context (the one referenced by the "this" keyword variable) to the other instance that has been passed into the compareTo(T) method. As a best practice there should be three possible values returned from the compareTo method:
- if the "this" instance is less than the instance passed in then -1 is returned
- if the two instances are equal then 0 is returned
- if the "this" instance is greater than the instance passed in then 1 is returned
In addition to these three return rules there is another rule that should always be followed when implementing the Comparable interface which is that a returned value of zero should also follow that the two objects are equal. This is referred to as being consistent with the class's equals implementation and, is necessary because sorted sets and maps implementation classes rely on the fact that compareTo of 0 means equality to determine whether to include a new object instance in the set or collection. This is quite important when it comes to classes that implement Comparable its very difficult to know apriori how a class will be used, meaning someone may unknowingly use it in a sorted set or map.
There are a couple of formal mathy / inductive reasoning proofs that are described in the official docs but, honestly the above three return value rules along with the consistency among compareTo and equals are sufficient.
Example Implementation of Comparable
To demonstrate implementing the Comparable interface I will utilize a class named MyPoint which represents an object constructed from X and Y coordinates and calculates the point's Euclidean distance from the origin as well as if that distance is an even integer or not.
package com.thecodinginterface.sorting;
public class MyPoint implements Comparable<MyPoint> {
private final double x;
private final double y;
private final int distance;
public MyPoint(double x, double y) {
this.x = x;
this.y = y;
distance = (int) Math.round(Math.sqrt((x * x) + (y * y)));
}
double getX() {
return x;
}
double getY() {
return y;
}
int getDistance() {
return distance;
}
boolean isEvenDistance() {
return distance % 2 == 0;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
long temp;
temp = Double.doubleToLongBits(x);
result = prime * result + (int) (temp ^ (temp >>> 32));
temp = Double.doubleToLongBits(y);
result = prime * result + (int) (temp ^ (temp >>> 32));
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
MyPoint other = (MyPoint) obj;
if (Double.doubleToLongBits(x) != Double.doubleToLongBits(other.x))
return false;
if (Double.doubleToLongBits(y) != Double.doubleToLongBits(other.y))
return false;
return true;
}
@Override
public int compareTo(MyPoint pt) {
int result = Double.compare(x, pt.x);
return result == 0 ? Double.compare(y, pt.y) : result;
}
@Override
public String toString() {
return String.format(
"{%s: x=%.1f, y=%.1f, distance=%d}",
getClass().getSimpleName(),
x,
y,
distance
);
}
}
Here the implementation of Comparable's compareTo method is such that MyPoint instances are ordered by X then Y coordinates. I don't know if that is a "natural" ordering as I'm not a Geometry wizard but, it sounds reasonable to me if I were to want to sort points.
Here is an example of using MyPoint class in a List<MyPoint> collection and what it looks like sorted.
List<MyPoint> points = Arrays.asList(
new MyPoint(2, 1),
new MyPoint(1, 2),
new MyPoint(1, 1),
new MyPoint(1, 3)
);
Collections.sort(points);Which results in a sorted list of MyPoint objects like so.
[
{MyPoint: x=1, y=1, distance=1},
{MyPoint: x=1, y=2, distance=2},
{MyPoint: x=1, y=3, distance=3},
{MyPoint: x=2, y=1, distance=2}
]Similarly here is the same example using a MyPoint[] array.
MyPoint[] points2 = new MyPoint[]{
new MyPoint(2, 1),
new MyPoint(1, 2),
new MyPoint(1, 1),
new MyPoint(1, 3)
};
Arrays.sort(points2);As a fun visualization I have built a JavaFX application which shows an animation to depict the points being added to a Euclidean coordinate system in their sort order for 500 randomly generated coordinate points.
Comparator<T> Interface
The Oracle Java Docs describe Comparator<T> as being another interface that is used to impose ordering which provide additional control over a class's Comparable implementation or where Comparable is not implemented at all. The Comparator interface is a functional interface in that it only contains one method to implement and it is not intended to be implemented in classes that are the target of sorting but, instead are intended for use in classes that apply sorting or simply as a lambda in conjunction with utility classes. The Comparator<T> interface contains several default and static methods but, the one purely functional method, compare(T) looks as follows.
public interface Comparator<T> {
int compare(T o1, T o2);
}Note that the compare(T, T) method accepts two generically typed parameters but, the same three best practice values are returned just like seen in the Comparable section:
- if o1 instance is less than o2 then -1 is returned
- if o1 and o2 are equal then 0 is returned
- if o1 is greater than o2 then 1 is returned
The docs again warn about the importance of the Comparator's compare method being consistent with the equals method of the generic T objects but, in my opinion this is a bit more relaxed in the case of Comparator implementations. I say this somewhat cautiously because it is true that if a Comparator is used to sort a set / map collection then the same problems with inconsistent behavior will occur as as described with the Comparable section. However, it is much easier to control and document Comparator implementations than the classes with Comparable that are likely to be used in such collections which implement Comparable. In fact, more often then not when I see Comparators used in practice they are often chosen because a "unnatural" or odd type of sorting specification is required.
Example Implementation of Comparator
This time I will demonstrate how I might use a Comparator to implement sorting behavior that differs from that of the default or "natural" sorting order provided by Comparable in the MyPoint class. I begin by implementing a Comparator which sorts by the distance from the origin which looks as follows.
Comparator<MyPoint> c1 = (a, b) -> Double.compare(a.getDistance(), b.getDistance());Note the use of the Double.compare(...) method here. All of the boxed primitive Java wrapper value classes have static compare methods and, it is best practice to use them whereever possible.
Now I sort the points List using the overloaded Collections.sort(List, Comparator) method like so.
Collections.sort(points, c1);This time the results of sorting looks as follows.
[
{MyPoint: x=1, y=1, distance=1},
{MyPoint: x=1, y=2, distance=2},
{MyPoint: x=2, y=1, distance=2},
{MyPoint: x=1, y=3, distance=3}
]Earlier I alluded to the fact earlier that Comparators are sometimes used to sort things in ways that may be a bit out of the norm so, to demonstrate this I will create a second Comparator that sorts MyPoint instances with even distances first then by distance second.
Comparator<MyPoint> c2 = (a, b) -> {
var aEven = a.isEvenDistance() ? 0 : 1;
var bEven = b.isEvenDistance() ? 0 : 1;
var c = Integer.compare(aEven, bEven);
return c == 0 ? Double.compare(a.getDistance(), b.getDistance()) : c;
};
Collections.sort(points, c2);Which results in the following sort order.
[
{MyPoint: x=1, y=2, distance=2},
{MyPoint: x=2, y=1, distance=2},
{MyPoint: x=1, y=1, distance=1},
{MyPoint: x=1, y=3, distance=3}
]Again, there is a similar sorting method on the Arrays class which takes an array and a Comparator to specify the sorting order which looks as follows.
MyPoint[] points2 = new MyPoint[]{
new MyPoint(2, 1),
new MyPoint(1, 2),
new MyPoint(1, 1),
new MyPoint(1, 3)
};
Arrays.sort(points2, c2);Here is another video showing the JavaFX sorting animation application depicting these last two sorting implementations.
Reversing the Sort Order
Another common use case with respect to implmenting Comparable / Comparator interfaces is to be able to sort things in reverse order. For lists of objects that implement the Comparable interface this is accomplished by calling the reverse method on the Collections utility class after first sorting the list with the previously mentioned Collections#sort method.
In my simply 4 item MyPoint list this looks as follows.
List<MyPoint> points = Arrays.asList(
new MyPoint(2, 1),
new MyPoint(1, 2),
new MyPoint(1, 1),
new MyPoint(1, 3)
);
Collections.sort(points);
Collections.reverse(points);Resulting in the following reverse sorted list with respect to the original sort order.
[
{MyPoint: x=2.0, y=1.0, distance=2},
{MyPoint: x=1.0, y=3.0, distance=3},
{MyPoint: x=1.0, y=2.0, distance=2},
{MyPoint: x=1.0, y=1.0, distance=1}
]Unfortunately there is not a matching Arrays.reverse(T[]) method but, one can still sort arrays in reverse order using a comparator which I will demonstrate shortly.
Reversing the sort order for a the list of MyPoint objects with respect to the Comparator that sorts first by even / odd then distance from origin uses same Collections#sort(List, Comparator) method but, the reversed method needs invoked on the comparator which returns a new comparator that inverts the ordering return values as follows.
List<MyPoint> points = Arrays.asList(
new MyPoint(2, 1),
new MyPoint(1, 2),
new MyPoint(1, 1),
new MyPoint(1, 3)
);
Comparator<MyPoint> c2 = (a, b) -> {
var aEven = a.isEvenDistance() ? 0 : 1;
var bEven = b.isEvenDistance() ? 0 : 1;
var c = Integer.compare(aEven, bEven);
return c == 0 ? Double.compare(a.getDistance(), b.getDistance()) : c;
};
Collections.sort(points, c2.reversed());And now MyPoint instances are sorted odd first then by distance in descending order.
[
{MyPoint: x=1.0, y=3.0, distance=3},
{MyPoint: x=1.0, y=1.0, distance=1},
{MyPoint: x=2.0, y=1.0, distance=2},
{MyPoint: x=1.0, y=2.0, distance=2}
]As promised this is how I can accomplish the same type of sorting using an array of MyPoint objects.
MyPoint[] points2 = new MyPoint[]{
new MyPoint(2, 1),
new MyPoint(1, 2),
new MyPoint(1, 1),
new MyPoint(1, 3)
};
Comparator<MyPoint> arrCmp = (a, b) -> {
var aEven = a.isEvenDistance() ? 0 : 1;
var bEven = b.isEvenDistance() ? 0 : 1;
var c = Integer.compare(aEven, bEven);
return c == 0 ? Double.compare(a.getDistance(), b.getDistance()) : c;
};
Arrays.sort(points2, arrCmp.reversed());For completeness here is a final video demonstrating the reverse sorting techniques using the JavaFX demo application.
Learn More About Java with These Resources
- I recently added a new Java reference book to my book shelf titled Java: The Complete Reference, Eleventh Edition by the well known Java author Herbert Schild which I highly recommend for anyone writing modern Java
- When it comes to best practices in Java, Effective Java, 3rd Ed is unparalleled
- Looking to learn or get refreshed on Java quickly? Have a look at my article High-Level Introduction to Java for Developers
thecodinginterface.com earns commision from sales of linked products such as the books above. This enables providing continued free tutorials and content so, thank you for supporting the authors of these resources as well as thecodinginterface.com
Conclusion
In this article I have demontrated how to use the Comparable and Comparator interfaces to control the way Arrays and Lists are sorted in Java. In addition I have explained why you would use one over the other in depending on the task being accomplished as well as described what I feel are the best practices around using these powerful interfaces.