Cosmin Mircea

Posted on Dec 24, 2019

Understanding Comparable and Comparator

#java #comparator #comparable #sorting

Overview:

Comparable interface:

Create a class implementing the Comparable interface

Comparator interface:

Create a class implementing of Comparator interface
Implement the Comparator interface through anonymous classes
Use the comparator helper methods

Why use Comparable or Comparator in Java: Sorting

There are a few ways of sorting a collection of objects in java

The first one is to use the inbuilt sorting methods to sort collections/arrays of Java primitive and wrapper classes

Array.sort(unsortedArray) : return type is void, unsorted array is sorted in place
Collections.sort(unsortedArrayList) : return type is void, unsorted list is sorted in place

The inbuilt method works out of the box for java primite or wrapper classes.

When it comes to custom objects, for the static sort method to work, those objects should be instances of classes implementing the Comparable interface

If you try to use Arrays.sort or Collections.sort on an array or list of objects which does not implement the Comparable interface you get the following runtime exception

|  Error:
|  no suitable method found for sort(java.util.ArrayList<Employee>)
|      method java.util.Collections.<T>sort(java.util.List<T>) is not applicable
|        (inference variable T has incompatible bounds
|          equality constraints: Employee
|          lower bounds: java.lang.Comparable<? super T>)
|      method java.util.Collections.<T>sort(java.util.List<T>,java.util.Comparator<? super T>) is not applicable
|        (cannot infer type-variable(s) T
|          (actual and formal argument lists differ in length))
|  Collections.sort(Employees);
|  ^--------------^

Comparable interface

To use the Arrays and Collections inbuilt sorting methods on custom classes, implement the Comparable interface
any class implementing this interface must provide implementation details for the compareTo(T obj) method. This method returns negative (if 'this' is <), 0, or positive number (if 'this' is >)
Comparable provides a single default way of sorting an object, and it can't be changed dinamically

public class Employee implements Comparable<Employee> {
  private int id;

  public Employee(int id){
    this.id = id;
  }

  public int getId(){
    return id;
  }

  //*****************
  @Override
  public int compareTo(Employee emp){
    return (this.id-emp.id)
  }
  //*****************

}

Comparator interface

with this we can define different implementations for ordering two instances of different classes
using comparator is the way of sorting two instances in different ways, when comapred to the Comparable interface which has a single default way
any class implementing this interface must implement the compare(Object o1, Object o2) method
you implement comparator to define your own way of sorting instances

To sort an Array or List of objects in Java with the Comparator Interface you need to start with an implementation of a type implementing the Collection interface :

List (interface)

ArrayList
Vector
Stack
LinkedList

Set (interface)

HashSet
LinkedHashSet

SortedSet (interface)

TreeSet

Queue (interface)

PriorityQueue

Dequeue (interface)

ArrayDeque

Map (interface)

HashMap

SortedMap (interface)

TreeMap

Tip: Comparators (anonymous classes assigned to a variable or classes implementing the comparator interface) can be passed to a sort method

Collections.sort(..accepts a comparator as an argument)
Arrays.sort(..accepts a comparator as an argument)

Comparator implementation through an anonymous classes

Use an anonymous class to create an instance of the Comparator and assign it to a variable. In this anonymous class implement the compare method

public static Comparator<Employee> grade1Emlpyees = new Comparator<Employee> {
  @Override
  public int compare(Employee e1, Employee e2) {
    return (int) (e1.getRank() - e2.getRank());
  }
}

you can sort a list of objects (instances of different classes as well) simply by creating a comparator and passing it to the sort method of Arrays and Collections
if an object has implemented the compareTo method of the Comparable interface, this can be overriden by using a Comparator, which will override the comparable interface implementation. Once this is done the sort method of Arrays and Collections can be used with the newly created comparator

// Create class
public class Employee {
  private int age;
  private String name;
  private double salary;

  public Employee(int age, String name, double salary) {
    this.age = age;
    this.name = name;
    this.salary = salary;
  }

  public int getAge(){ return this.age;}
  public String getName() {return this.name;}
  public double getSalary() {return this.salary;}
}

// Create Comparator with an Anonymous class

public Comparator<Employee> compareByAge = new Comparator<Employee>(){
  @Override
  public int compare(Employee e1, Employee e2){
    return e1.getAge() - e2.getAge();
  }
}

//Create the lists
Employee e1 = new Employee(10, "Employee1", 100.00);

Employee e2 = new Employee(12, "Employee2", 100.00);

Employee e3 = new Employee(11, "Employee3", 100.00);

ArrayList<Employee> employeeCollection = new ArrayList<>(List.of(e1,e2,e3));
Employee[] employeeArray =  {e1,e2,e3};

// User Array sort and Collection sort

Collections.sort(employeeCollection, compareByAge);
Arrays.sort(employeeArray, compareByAge);

//After
for (Employee e: employeeCollection) {
  System.out.println(e.getAge());
}

for (Employee e: employeeArray) {
  System.out.println(e.getAge() + " " + e.getName() + " " + e.getSalary());
}

Comparator class implementation

You can implement a comparator by creating a class and extending the comparator

public class EmployeeComparatorByAge implements Comparator<Employee> {
  @Override
  public int compare(Employee e1, Employee e2) {
    return e1.getAge() - e2.getAge();
  }
}

//use the new keyword to create an instance of the comparator withouth parameters (uses default initializer = empty one)

Collections.sort(employeeCollection, new EmployeeComparatorByAge());
Arrays.sort(employeeArray, new EmployeeComparatorByAge());

Comparator utility methods used to create a Comparator

If the object does not implement the comparable interface, we can use the Comparator utility methods to create Comparators to sort on a field, chain comparators or reverse orders

Tip:

if you have an implementation of compareTo or compare in your Pojo, you can use the sort method
otherwise, you can sort a collection by passing a comparator to the sort method

Create a POJO

public class Locations implements Comparator<Locations> {

    private double longitude;
    private double latitude;
    private UUID uuid;
    private Date date;

    public Locations(double longitude, double latitude) {
        this.longitude = longitude;
        this.latitude = latitude;
        this.uuid = UUID.randomUUID();
        this.date = new Date();
    }

    public double getLongitude() {
        return longitude;
    }

    public double getLatitude() {
        return latitude;
    }

    @Override
    public int compare(Locations o1, Locations o2) {
        return 0;
    }
}

Use the Comparator utility methods

comparing => returns a comparator
thenComparing (for chaining comparators) => returns a comparator used in chaining


Comparator sortByLongitude = Comparator.comparing(Locations::getLongitude()); // => this returns a Comparator that can be used in Collections.sort
Collections.sort(listOfLocationObjects, sortByLongitude);

Comparator groupSort = Comparator.comparing(Locations::getLongitude).thenComparing(Locations::getDate()).thenComparing(Locations::getId()); //=> sort first by longitude, then by date and then finalize with a sort by ID;
Collections.sort(listOgObjects, groupSort);

//Reverse order
Comparator groupSortReversed = Comparator.comparing(Locations::getLongitude).reversed();
Collections.sort(listOgObjects, groupSortReversed);