Use Java’s world-class sorting algorithms on your custom objects

A lot of people don’t realize that the standard Java libraries are kept up-to-date with world-class sorting algorithms. For example, Java 7 released with an implementation of Timsort for Arrays.sort.

Class/Method Type of Collection Algorithm
Arrays.sort array timsort (objects) or dual-pivot quicksort (certain primitives)
Arrays.parallelSort array merge sort
Collections.sort List merge sort

If you’re not familiar with the Comparable or Comparator interfaces, now might be the time. As long as your object implements Comparable you can use the above sort methods from the standard library. There are often great uses for Comparator as well, especially when you want multiple ways to sort the same objects. For the rest of the post I’ll deal just with Comparable.

Containers

A practical example

Let’s say your call center receives calls from customers which are then handled by different agents. For the sake of the example, we’ll limit this code only to two data points: date/time call is received and the agent who handles it.

The CustomerCall object

We’ll use standard types of java.util.Date and java.lang.String so you can easily run this code on your machine without any special libraries.

Here’s the POJO that can represent a call.

import java.util.Date;

public class CustomerCall {

  private String agentName;
  private Date callReceived;

  public CustomerCall(String agentName, Date callReceived) {
    this.agentName = agentName;
    this.callReceived = callReceived;
  }

  public String getAgentName() {
    return agentName;
  }

  public Date getCallReceived() {
    return callReceived;
  }

}

You should save this in a file called CustomerCall.java, and compile it now if you plan to follow along.

Sorting Customer Calls

Now let’s say that you’re the call center supervisor and at the end of each day you want to get a little report of the day’s calls. It would make sense for a supervisor to want to see a list of the calls first sorted by each agent, and then sorted by the time that the call actually occurred.

Here is a little test class that can help us see Collections.sort in action:

import java.lang.Math;
import java.lang.Thread;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
import java.util.List;

public class CustomerCallsReport {

  static void pauseAtLeastOneSecond() {
    int millisToPause = new Double((Math.random() + 1D) * 1000).intValue();
    System.out.print("  -- generating calls...");
    try {
     Thread.sleep(millisToPause);
    } catch(InterruptedException ex) {}
  }

  static List<CustomerCall> getCustomerCallsForToday() {
    List<CustomerCall> todaysCalls = new ArrayList<>();
    addCall(todaysCalls, new CustomerCall("Lynn", new Date()));
    addCall(todaysCalls, new CustomerCall("Wayne", new Date()));
    addCall(todaysCalls, new CustomerCall("Deepak", new Date()));
    addCall(todaysCalls, new CustomerCall("Lynn", new Date()));
    addCall(todaysCalls, new CustomerCall("Deepak", new Date()));
    addCall(todaysCalls, new CustomerCall("Wayne", new Date()));
    addCall(todaysCalls, new CustomerCall("Wayne", new Date()));
    addCall(todaysCalls, new CustomerCall("Lynn", new Date()));
    addCall(todaysCalls, new CustomerCall("Deepak", new Date()));
    System.out.println("\n");
    return todaysCalls;
  }

  static void addCall(List<CustomerCall> callList, CustomerCall call) {
    pauseAtLeastOneSecond();
    callList.add(call);
  }

  static void printCalls(List<CustomerCall> todaysCalls) {
    System.out.println();
    String currentAgent = "";
    for(CustomerCall call : todaysCalls) {
      if(!currentAgent.equals(call.getAgentName())) {
        currentAgent = call.getAgentName();
        System.out.printf("%nAgent: %s%n", currentAgent);
      }
      System.out.printf("Call time: %s%n", call.getCallReceived());
    }
  }

  public static void main(String[] args) {
    List<CustomerCall> todaysCalls = getCustomerCallsForToday();
    System.out.println("\nBefore sort:\n");
    printCalls(todaysCalls);
    System.out.println("\nAfter sort:\n");
    Collections.sort(todaysCalls);
    printCalls(todaysCalls);
  }

}

You can basically ignore the first three methods as they are just creating a List of CustomerCall objects for us. Looking at the printCalls method, you can see that it expects a sorted list of customer calls so that it can print each agent’s name and then all the calls that they had for the day. It will have output like this, if the list is actually sorted:

Agent: Deepak
Call time: Wed Nov 18 13:27:14 PST 2015
Call time: Wed Nov 18 13:27:17 PST 2015
Call time: Wed Nov 18 13:27:24 PST 2015

Agent: Lynn
Call time: Wed Nov 18 13:27:11 PST 2015
Call time: Wed Nov 18 13:27:15 PST 2015
Call time: Wed Nov 18 13:27:22 PST 2015

Agent: Wayne
Call time: Wed Nov 18 13:27:13 PST 2015
Call time: Wed Nov 18 13:27:18 PST 2015
Call time: Wed Nov 18 13:27:20 PST 2015

Unfortunately, if you try to compile this (I used Java 8) you will see:

CustomerCallsReport.java:33: error: no suitable method found for sort(List<CustomerCall>)
    Collections.sort(todaysCalls);
               ^
    method Collections.<T#1>sort(List<T#1>) is not applicable
      (inference variable T#1 has incompatible bounds
        equality constraints: CustomerCall
        upper bounds: Comparable<? super T#1>)
    method Collections.<T#2>sort(List<T#2>,Comparator<? super T#2>) is not applicable
      (cannot infer type-variable(s) T#2
        (actual and formal argument lists differ in length))
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<? super T#1> declared in method <T#1>sort(List<T#1>)
    T#2 extends Object declared in method <T#2>sort(List<T#2>,Comparator<? super T#2>)
1 error

This gibberish translates to: “You didn’t implement Comparable in your CustomerCall class!”

Implementing Comparable in CustomerCall

Let’s implement Comparable now. The Comparable interface only has one method: compareTo. In this case, we can write a compareTo method that first sorts by agent name, and then by agent date, by in turn using the compareTo method of each of those things. Like this:

public int compareTo(CustomerCall other) {
    if(this.agentName.compareTo(other.agentName) == 0) {
      return this.callReceived.compareTo(other.callReceived);
    } else {
      return this.agentName.compareTo(other.agentName);
    }
  }

Hopefully this is clear. It literally says, “if the agent names are the same then return the result of comparing when the call was received, but if the agent names are different, then return the result of comparing the agent names.”

Of course don’t forget to add the “implements Comparable<CustomerCall>” to the class signature. The final CustomerCall class will look like:

import java.util.Date;

public class CustomerCall implements Comparable<CustomerCall> {

  private String agentName;
  private Date callReceived;

  public CustomerCall(String agentName, Date callReceived) {
    this.agentName = agentName;
    this.callReceived = callReceived;
  }

  public String getAgentName() {
    return agentName;
  }

  public Date getCallReceived() {
    return callReceived;
  }

  public int compareTo(CustomerCall other) {
    if(this.agentName.compareTo(other.agentName) == 0) {
      return this.callReceived.compareTo(other.callReceived);
    } else {
      return this.agentName.compareTo(other.agentName);
    }
  }

}

The final result!

Now try to recompile CustomerCallsReport. That should go great now!

And the resulting output from running it should be similar to:

  -- generating calls...  -- generating calls...  -- generating calls...  -- generating calls...  -- generating calls...  -- generating calls...  -- generating calls...  -- generating calls...  -- generating calls...


Before sort:

Agent: Lynn
Call time: Wed Nov 18 13:27:11 PST 2015

Agent: Wayne
Call time: Wed Nov 18 13:27:13 PST 2015

Agent: Deepak
Call time: Wed Nov 18 13:27:14 PST 2015

Agent: Lynn
Call time: Wed Nov 18 13:27:15 PST 2015

Agent: Deepak
Call time: Wed Nov 18 13:27:17 PST 2015

Agent: Wayne
Call time: Wed Nov 18 13:27:18 PST 2015
Call time: Wed Nov 18 13:27:20 PST 2015

Agent: Lynn
Call time: Wed Nov 18 13:27:22 PST 2015

Agent: Deepak
Call time: Wed Nov 18 13:27:24 PST 2015

After sort:



Agent: Deepak
Call time: Wed Nov 18 13:27:14 PST 2015
Call time: Wed Nov 18 13:27:17 PST 2015
Call time: Wed Nov 18 13:27:24 PST 2015

Agent: Lynn
Call time: Wed Nov 18 13:27:11 PST 2015
Call time: Wed Nov 18 13:27:15 PST 2015
Call time: Wed Nov 18 13:27:22 PST 2015

Agent: Wayne
Call time: Wed Nov 18 13:27:13 PST 2015
Call time: Wed Nov 18 13:27:18 PST 2015
Call time: Wed Nov 18 13:27:20 PST 2015

You can see that before the list is actually sorted, the output looks terrible! But afterword, we see exactly what we want! Ah! That’s better!

Final words

If you have never used this wonderful interface for your custom objects, then give it a try next chance you get. And let me know if you run across any questions by posting in the comments below!

Leave a Reply

Your email address will not be published. Required fields are marked *