JavaAdvanced Sorting (Comparator and Comparable)
Java Advanced Sorting
In theList 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.
TheComparator andComparable 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 theComparator interface is called a comparator.
TheComparator interface allows you to create a class with acompare() method that compares two objects to decide which one should go first in a list.
Thecompare() 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 theComparator interface might look something like this:
// Sort Car objects by yearclass 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 carsComparator 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 classclass 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 comparatorclass 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 thecompare() 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
TheComparable interface allows an object to specify its own sorting rule with acompareTo() method.
ThecompareTo() 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, thecompareTo() 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 theComparable interface, such asString andInteger.
This is why strings and numbers do not need a comparator to be sorted.
An object that implements theComparable 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 theComparable interface instead of a comparator:
Example
import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;// Define a Car class which is comparableclass 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 bif(a.year > b.year) return 1; // a is greater than breturn 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;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 theComparable interface when possible, but theComparator interface is more powerful because it allows you to sort any kind of object even if you cannot change its code.
