Java Advanced Sorting (Comparator and Comparable)
Java Advanced Sorting
In the List Sorting Chapter, you learned how to sort lists alphabetically and numerically, but what if the list has objects in it?
To sort objects you need to specify a rule that decides how objects should be sorted. For example, if you have a list of cars you might want to sort them by year, 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 {
public int compare(Object obj1, Object obj2) {
// Make sure that the objects are Car objects
Car a = (Car) obj1;
Car b = (Car) obj2;
// Compare the objects
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
}
}
To use the comparator, pass it as an argument into a sorting method:
// Use a comparator to sort the cars
Comparator 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 {
public int compare(Object obj1, Object obj2) {
// Make sure that the objects are Car objects
Car a = (Car) obj1;
Car b = (Car) obj2;
// Compare the year of both objects
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 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, (obj1, obj2) -> {
Car a = (Car) obj1;
Car b = (Car) obj2;
if (a.year < b.year) return -1;
if (a.year > b.year) return 1;
return 0;
});
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 {
public int compare(Object obj1, Object obj2) {
// Make sure the objects are integers
Integer a = (Integer)obj1;
Integer b = (Integer)obj2;
// 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 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 {
public String brand;
public String model;
public int year;
// Decide how this object compares to other objects
public int compareTo(Object obj) {
Car other = (Car)obj;
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;
import java.util.Comparator;
// Define a Car class which is comparable
class Car implements Comparable {
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(Object obj) {
Car other = (Car)obj;
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 b
But 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;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.
