Java Advanced Sorting (Comparator and Comparable)
Java Advanced Sorting
In the List Sorting Chapter, you learned how to sort lists of strings and numbers with Collections.sort().
But what if the list has your own objects in it, like cars? Then Java gives an error, because it does not know how to sort them. Should the cars be sorted by brand, by model, or by year?
ArrayList<Car> myCars = new ArrayList<Car>();
myCars.add(new Car("BMW", "X5", 1999));
myCars.add(new Car("Honda", "Accord", 2006));
myCars.add(new Car("Ford", "Mustang", 1970));
Collections.sort(myCars); // ErrorTo sort objects you need to specify a rule that decides how objects should be sorted. For example, the rule could be that cars with an earlier year go first.
The Comparator and Comparable interfaces allow you to specify what rule is used to sort objects.
Being able to specify a sorting rule also allows you to change how strings and numbers are sorted.
Comparators
An object that implements the Comparator interface is called a comparator.
The Comparator interface allows you to create a class with a compare() method that compares two objects to decide which one should go first in a list.
The compare() method should return a number which is:
- Negative if the first object should go first in a list.
- Positive if the second object should go first in a list.
- Zero if the order does not matter.
A class that implements the Comparator interface might look something like this:
// Sort Car objects by year
class SortByYear implements Comparator<Car> {
public int compare(Car a, Car b) {
if (a.year < b.year) return -1; // The first car has a smaller year
if (a.year > b.year) return 1; // The first car has a larger year
return 0; // Both cars have the same year
}
}The <Car> part tells Java that this comparator compares Car objects, just like ArrayList<Car> holds Car objects.
For example, if you compare the BMW from 1999 with the Honda from 2006, compare() returns -1, because 1999 is smaller than 2006. So the BMW goes first.
To use the comparator, pass it as an argument into a sorting method:
// Use a comparator to sort the cars
Comparator<Car> myComparator = new SortByYear();
Collections.sort(myCars, myComparator);Here is a complete example using a comparator to sort a list of cars by year:
Example
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
// Define a Car class
class Car {
public String brand;
public String model;
public int year;
public Car(String b, String m, int y) {
brand = b;
model = m;
year = y;
}
}
// Create a comparator
class SortByYear implements Comparator<Car> {
public int compare(Car a, Car b) {
// Compare the year of both cars
if (a.year < b.year) return -1; // The first car has a smaller year
if (a.year > b.year) return 1; // The first car has a larger year
return 0; // Both cars have the same year
}
}
public class Main {
public static void main(String[] args) {
// Create a list of cars
ArrayList<Car> myCars = new ArrayList<Car>();
myCars.add(new Car("BMW", "X5", 1999));
myCars.add(new Car("Honda", "Accord", 2006));
myCars.add(new Car("Ford", "Mustang", 1970));
// Use a comparator to sort the cars
Comparator<Car> myComparator = new SortByYear();
Collections.sort(myCars, myComparator);
// Display the cars
for (Car c : myCars) {
System.out.println(c.brand + " " + c.model + " " + c.year);
}
}
}Using a Lambda Expression
To make the code shorter, the comparator can be replaced with a lambda expression which has the same arguments and return value as the compare() method:
Example
Use a lambda expression as a comparator:
Collections.sort(myCars, (a, b) -> {
if (a.year < b.year) return -1;
if (a.year > b.year) return 1;
return 0;
});Java knows that myCars holds Car objects, so a and b are cars.
Sort by Text
To sort the cars by a text value, like the brand, use the compareTo() method of the strings. It compares two strings alphabetically, and returns a negative number, a positive number or zero, just like compare(). So you can return its result directly:
Example
Sort the cars by brand:
Collections.sort(myCars, (a, b) -> a.brand.compareTo(b.brand));Special Sorting Rules
Comparators can also be used to make special sorting rules for strings and numbers. In this example we use a comparator to list all of the even numbers before the odd ones:
Example
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
class SortEvenFirst implements Comparator<Integer> {
public int compare(Integer a, Integer b) {
// Check each number to see if it is even
// A number is even if the remainder when dividing by 2 is 0
boolean aIsEven = (a % 2) == 0;
boolean bIsEven = (b % 2) == 0;
if (aIsEven == bIsEven) {
// If both numbers are even or both are odd then use normal sorting rules
if (a < b) return -1;
if (a > b) return 1;
return 0;
} else {
// If a is even then it goes first, otherwise b goes first
if (aIsEven) {
return -1;
} else {
return 1;
}
}
}
}
public class Main {
public static void main(String[] args) {
ArrayList<Integer> myNumbers = new ArrayList<Integer>();
myNumbers.add(33);
myNumbers.add(15);
myNumbers.add(20);
myNumbers.add(34);
myNumbers.add(8);
myNumbers.add(12);
Comparator<Integer> myComparator = new SortEvenFirst();
Collections.sort(myNumbers, myComparator);
for (int i : myNumbers) {
System.out.println(i);
}
}
}The Comparable Interface
The Comparable interface allows an object to specify its own sorting rule with a compareTo() method.
The compareTo() method takes an object as an argument and compares the comparable with the argument to decide which one should go first in a list.
Like the comparator, the compareTo() method returns a number which is:
- Negative if the comparable should go first in a list.
- Positive if the other object should go first in a list.
- Zero if the order does not matter.
Many native Java classes implement the Comparable interface, such as String and Integer.
This is why strings and numbers do not need a comparator to be sorted.
An object that implements the Comparable interface might look something like this:
class Car implements Comparable<Car> {
public String brand;
public String model;
public int year;
// Decide how this object compares to other objects
public int compareTo(Car other) {
if (year < other.year) return -1; // This object is smaller than the other one
if (year > other.year) return 1; // This object is larger than the other one
return 0; // Both objects are the same
}
}Here is the same example as before but using the Comparable interface instead of a comparator:
Example
import java.util.ArrayList;
import java.util.Collections;
// Define a Car class which is comparable
class Car implements Comparable<Car> {
public String brand;
public String model;
public int year;
public Car(String b, String m, int y) {
brand = b;
model = m;
year = y;
}
// Decide how this object compares to other objects
public int compareTo(Car other) {
if (year < other.year) return -1; // This object is smaller than the other one
if (year > other.year) return 1; // This object is larger than the other one
return 0; // Both objects are the same
}
}
public class Main {
public static void main(String[] args) {
// Create a list of cars
ArrayList<Car> myCars = new ArrayList<Car>();
myCars.add(new Car("BMW", "X5", 1999));
myCars.add(new Car("Honda", "Accord", 2006));
myCars.add(new Car("Ford", "Mustang", 1970));
// Sort the cars
Collections.sort(myCars);
// Display the cars
for (Car c : myCars) {
System.out.println(c.brand + " " + c.model + " " + c.year);
}
}
}A Common Sorting Trick
The most obvious way to sort two numbers naturally is to write something like this:
if (a.year < b.year) return -1; // a is less than b
if (a.year > b.year) return 1; // a is greater than b
return 0; // a is equal to bBut it can actually be done with just a single line:
return a.year - b.year;This trick can also be used to easily sort things in reverse:
return b.year - a.year;With a lambda expression, the whole sorting rule fits on one line:
Collections.sort(myCars, (a, b) -> a.year - b.year);Comparator vs. Comparable
A comparator is an object with one method that is used to compare two different objects.
A comparable is an object which can compare itself with other objects.
It is easier to use the Comparable interface when possible, but the Comparator interface is more powerful because it allows you to sort any kind of object even if you cannot change its code.
