CMUQ 15-121 Comparators

1. Introduction

Now that we’ve talked about different sorting algorithms, let’s look at how Java’s built-in library handles sorting. In this set of notes we’ll look at sorting arrays, sorting collections (like an ArrayList), and how you can setup your own objects so they can be sorted using the library sort routines.

2. Sorting an Array

If you have an array that you want to sort, you can simply use Arrays.sort() from java.util.Arrays. Here is an example:

int[] someArray = { 54, 37, 48, 23, 84, 73, 21 };
Arrays.sort(someArray);
System.out.println(Arrays.toString(someArray));

This will output [21, 23, 37, 48, 54, 73, 84]. Note that Arrays.sort() does not return a sorted array. It sorts the existing array in-place.

3. Sorting a Collection

If you have a collection (such as Java’s ArrayList and LinkedList) then you can simply use Collections.sort() from java.util.Collections. Here is an example:

ArrayList<Integer> someList = new ArrayList<Integer>();
someList.add(54);
someList.add(37);
someList.add(48);
someList.add(23);
someList.add(84);
someList.add(73);
someList.add(21);
Collections.sort(someList);
System.out.println(someList);

This will output [21, 23, 37, 48, 54, 73, 84]. Note that much like dealing with arrays, Collections.sort() does not return a sorted collection. It sorts the existing collection in-place.

4. Algorithms Used

When sorting using Arrays.sort():

When sorting using Collects.sort():

5. Making Objects Comparable

Both of these techniques for sorting things work on either primitive types or objects. However, when dealing with objects, we need to consider an important complication. Consider the following sample class:

public class Person {
    private String firstName;
    private String lastName;
    private int age;

    public Person(String firstName, String lastName, int age) {
        this.firstName = firstName;
        this.lastName = lastName;
        this.age = age;
    }

    public String getFirstName() {
        return firstName;
    }

    public String getLastName() {
        return lastName;
    }

    public int getAge() {
        return age;
    }

    public String toString() {
        return "Person [firstName=" + firstName + ", lastName=" + lastName + ", age=" + age + "]";
    }

}

Now, imagine we have an ArrayList of Person objects and we want to sort it with Collections.sort(). How will Java know how to order the objects? Should it sort by first name? last name? age? Some combination? The Person class doesn’t specify how to compare two people, and so we can’t sort them.

5.1. Natural Order

If you want to be able to sort a set of objects, you need to specify the natural ordering for those objects. A natural ordering can be thought of as the default ordering for that kind of object. “When in doubt, order them like this.”

Now that we know what a natural order is, we need to look at how to specify it in Java.

5.2. The Comparator

In order to specify the natural ordering of an object, that object needs to be comparable to other objects of the same type. We do that by having the class implement the Comparable interface. As part of that interface, the class must have a compareTo method. Let’s look at an example that defines a natural ordering based on the age of the person:

public class Person implements Comparable<Person> {
    private String firstName;
    private String lastName;
    private int age;

    public Person(String firstName, String lastName, int age) {
        this.firstName = firstName;
        this.lastName = lastName;
        this.age = age;
    }

    public String getFirstName() {
        return firstName;
    }

    public String getLastName() {
        return lastName;
    }

    public int getAge() {
        return age;
    }

    public String toString() {
        return "Person [firstName=" + firstName + ", lastName=" + lastName + ", age=" + age + "]";
    }

    /**
     * Compare this person to another Person.
     * 
     * @param p The other Person to compare to.
     * 
     * @returns -1 if this person is less-than the other person, 1 if this person is
     *          greater than the other person, and 0 otherwise.
     */
    public int compareTo(Person p) {
        if (this.age < p.age) {
            return -1;
        } else if (this.age > p.age) {
            return 1;
        } else {
            return 0;
        }
    }
}

There are a few important things to notice here.

  1. The Person class now implements Comparable<Person>. This tells Java that a Person object can be compared to other Person objects.
  2. The new compareTo method should compare the current object (this) to the object passed as a parameter (p) and return a negative number if this < p, a positive number if this > p, and 0 if this == p. In this case, since we’re going to compare based on age, this makes the implementation straight-forward.

5.3. A More Complicated Example

Our compareTo method is actually not very good. It specifies that objects are equal based only on their age (which is bad) and ignores all the other fields. Let’s come up with a better way to order people. Here’s a simple proposal: Order by last name, then first name, then age. This means that last name is most important, but if those are equal than look at first name, too. If both last and first name are equal, then look at age. Here is an example with a better compareTo method:

public class Person implements Comparable<Person> {
    private String firstName;
    private String lastName;
    private int age;

    public Person(String firstName, String lastName, int age) {
        this.firstName = firstName;
        this.lastName = lastName;
        this.age = age;
    }

    public String getFirstName() {
        return firstName;
    }

    public String getLastName() {
        return lastName;
    }

    public int getAge() {
        return age;
    }

    public String toString() {
        return "Person [firstName=" + firstName + ", lastName=" + lastName + ", age=" + age + "]";
    }

    /**
     * Compare this person to another Person.
     * 
     * @param p The other Person to compare to.
     * 
     * @returns -1 if this person is less-than the other person, 1 if this person is
     *          greater than the other person, and 0 otherwise.
     */
    public int compareTo(Person p) {
        // Check last name
        int ret = this.lastName.compareTo(p.lastName);
        if (ret != 0) {
            return ret;
        }

        // Last names were equal, now check first names
        ret = this.firstName.compareTo(p.firstName);
        if (ret != 0) {
            return ret;
        }

        // Both last and first names were equal, now do age
        if (this.age < p.age) {
            return -1;
        } else if (this.age > p.age) {
            return 1;
        } else {
            return 0;
        }
    }
}

Note that this method makes use of the existing compareTo method for String. (That’s because the String class implements Comparable<String>, so that method exists.)

If we do this, then the following code:

ArrayList<Person> theList = new ArrayList<Person>();
theList.add(new Person("Fred", "Jones", 40));
theList.add(new Person("Bob", "Jones", 25));
theList.add(new Person("Fred", "Jones", 15));
theList.add(new Person("Tamim", "AlKuwari", 35));
Collections.sort(theList);
System.out.println(theList);

Produces the following order:

Person [firstName=Tamim, lastName=AlKuwari, age=35]
Person [firstName=Bob, lastName=Jones, age=25]
Person [firstName=Fred, lastName=Jones, age=15]
Person [firstName=Fred, lastName=Jones, age=40]

Which is sorted example how we want.

6. Sorting By an Order Other than Natural

So, you have an object and you’ve given it a natural ordering. What if, in your program, you want to sort by something else, just once or a few times. For example, let’s say that I do want to order by age, even though that isn’t the natural ordering. (Maybe I want to find the youngest people in the list.) You don’t change the natural ordering, instead you create a new class that implements Comparator and has a compare method that does what you want and specify it as an argument to the sort method. Here is an example:

public class CompareAge implements Comparator<Person> {

    public int compare(Person p1, Person p2) {
        if (p1.getAge() < p2.getAge()) {
            return -1;
        } else if (p1.getAge() > p2.getAge()) {
            return 1;
        } else {
            return 0;
        }
    }
}

This is a new class that implements the Comparator interface. That interface requires a compare method that can be used to compare two objects. It has the same return convention as compareTo from before.

If you want to use this comparator to actually sort something:

ArrayList<Person> theList = new ArrayList<Person>();
theList.add(new Person("Fred", "Jones", 40));
theList.add(new Person("Bob", "Jones", 25));
theList.add(new Person("Fred", "Jones", 15));
theList.add(new Person("Tamim", "AlKuwari", 35));

CompareAge c = new CompareAge();
Collections.sort(theList, c);

System.out.println(theList);

Which produces the following order:

Person [firstName=Fred, lastName=Jones, age=15]
Person [firstName=Bob, lastName=Jones, age=25]
Person [firstName=Tamim, lastName=AlKuwari, age=35]
Person [firstName=Fred, lastName=Jones, age=40]

So, if you want to sort by something other the natural ordering, you can simply create a new object that implements Comparator and use that with the existing sort methods.