Sorting List Collections Examples

In Java, it’s pretty easy to sort elements in a list collection using the Collections.sort() static utility method. This method has two forms as follows:

• • void sort(List<T> list): sorts the list into ascending order according to its elements’ natural ordering.
  • void sort(List<T> list, Comparator<? super T> c): sorts the list into the order specified by the given comparator.

Behind the scenes, the sort operation uses a merge sort algorithm which is slightly optimized to be fast and stable:

• • Fast: it guarantees O(n log n) performance in average and worst cases, and runs faster if the original list is nearly sorted.
  • Stable: it preservers the order the equal elements so it’s useful for sorting the list repeatedly on different attributes.

Let’s dive into some detailed examples.

Sorting a list according to natural ordering of elements

Basically, a list can be sorted if only all of its elements are mutually comparable by implementing the Comparable interface. If a class implements the Comparable interface, it is considered as having natural ordering which allows objects of that class to be sorted by the Collections.sort(list) method.

All basic data type wrapper classes in Java have natural ordering: String, Character, Byte, Date, Integer, Float, etc. Here are some examples:

Sorting a list of Strings:

List<String> listStrings = Arrays.asList("Orange", "Grape", "Apple", "Lemon", "Banana");

System.out.println("Before sorting: " + listStrings);

Collections.sort(listStrings);

System.out.println("After sorting: " + listStrings);

Output:

Before sorting: [Orange, Grape, Apple, Lemon, Banana]

After sorting: [Apple, Banana, Grape, Lemon, Orange]

Sorting a list of Characters:

List<Character> listCharacters = Arrays.asList('F', 'C', 'A', 'B', 'Z', 'E', 'K', 'P');

System.out.println("Before sorting: " + listCharacters);

Collections.sort(listCharacters);

System.out.println("After sorting: " + listCharacters);




Output:

Before sorting: [F, C, A, B, Z, E, K, P]

After sorting: [A, B, C, E, F, K, P, Z]

Sorting a list of Dates:

List<Date> listDates = new ArrayList<Date>();

DateFormat dateFormatter = new SimpleDateFormat("yyyy-MM-dd");

try {

    listDates.add(dateFormatter.parse("2013-09-30"));

    listDates.add(dateFormatter.parse("2013-07-06"));

    listDates.add(dateFormatter.parse("2013-11-28"));

} catch (ParseException ex) {

    System.err.print(ex);

}

System.out.println("Before sorting: " + listDates);

Collections.sort(listDates);

System.out.println("After sorting: " + listDates);

Output:

Before sorting: [Mon Sep 30 00:00:00 ICT 2013, Sat Jul 06 00:00:00 ICT 2013, Thu Nov 28 00:00:00 ICT 2013]

After sorting: [Sat Jul 06 00:00:00 ICT 2013, Mon Sep 30 00:00:00 ICT 2013, Thu Nov 28 00:00:00 ICT 2013]

Sorting a list whose elements of a custom type

What if a list contains elements of a custom type other than the pre-defined types above? Well, in that case, we have to make the class of the custom type implements the Comparable interface. Suppose that we have a custom type called Employee as follows:

public class Employee {

    private String name;

    private int age;

    private int salary;

    public Employee(String name, int age, int salary) {

        this.name = name;

        this.age = age;

        this.salary = salary;

    }

    // getters and setters

}

If we try to sort a list whose elements of the type Employee above, the sort(list) method will throw aClassCastException. Now, let’s the Employee class implemented the Comparable interface as follows:

public class Employee implements Comparable<Employee> {

    // variables, getters and setters...

    @Override

    public int compareTo(Employee employee) {

        return employee.salary - this.salary;

    }

}

As we see, the Employee class now overrides the compareTo() method from the Comparable interface. This method simply compares the salary between this employee and another. And override the toString() method as follows:

public String toString() {

    return String.format("(%s, %d, %d)", name, age, salary);

}

We override the toString() method of the Employee class so that the returned string will be used when printing the list content.

The following code example creates a list of employees and sorts it based on the descending order of salary:

List<Employee> listEmployees = new ArrayList<Employee>();

listEmployees.add(new Employee("Tom", 45, 80000));

listEmployees.add(new Employee("Sam", 56, 75000));

listEmployees.add(new Employee("Alex", 30, 120000));

listEmployees.add(new Employee("Peter", 25, 60000));

System.out.println("Before sorting: " + listEmployees);

Collections.sort(listEmployees);

System.out.println("After sorting: " + listEmployees);

Output:

Before sorting: [(Tom, 45, 80000), (Sam, 56, 75000), (Alex, 30, 120000), (Peter, 25, 60000)]

After sorting: [(Alex, 30, 120000), (Tom, 45, 80000), (Sam, 56, 75000), (Peter, 25, 60000)]

Sorting a list using a Comparator

The second form of the sort method takes a Comparator implementation that defines the ordering of elements in the list externally:

Collections.sort(list, Comparator)

In this case, the type of the elements need not implement the Comparator interface. This would be useful if we need to sort a list of custom objects which we cannot modify its class; or if we don’t want to rely on the natural ordering of the elements. The following code is example of a comparator that compares two employees based on their ages:

package net.codejava.collections;

import java.util.Comparator;

/**

 * This comparator compares two employees by their ages.

 * @author www.codejava.net

 *

 */

public class EmployeeAgeComparator implements Comparator<Employee> {

    @Override

    public int compare(Employee emp1, Employee emp2) {

        return emp1.getAge() - emp2.getAge();

    }

}

And the following code snippet sorts a list of employees using the above comparator:

List<Employee> listEmployees = new ArrayList<Employee>();

listEmployees.add(new Employee("Tom", 45, 80000));

listEmployees.add(new Employee("Sam", 56, 75000));

listEmployees.add(new Employee("Alex", 30, 120000));

listEmployees.add(new Employee("Peter", 25, 60000));

System.out.println("Before sorting: " + listEmployees);

Collections.sort(listEmployees, new EmployeeAgeComparator());

System.out.println("After sorting: " + listEmployees);

Output:

Before sorting: [(Tom, 45, 80000), (Sam, 56, 75000), (Alex, 30, 120000), (Peter, 25, 60000)]

After sorting: [(Peter, 25, 60000), (Alex, 30, 120000), (Tom, 45, 80000), (Sam, 56, 75000)]