Sorting in Collections

You can sort List collections using the java.util.Collections.sort() method. You can sort these two types of List's.

1. List
2. LinkedList

Sorting Objects by their Natural Order

To sort a List you do this:

List list = new ArrayList();

//add elements to the list

Collections.sort(list);

When sorting a list like this the elements are ordered according to their "natural order". For objects to have a natural order they must implement the interface java.lang.Comparable. In other words, the objects must be comparable to determine their order. Here is how the Comparable interface looks:

public interface Comparable<T> {
  int compareTo(T o);
}

The compareTo() method should compare this object to another object, return an int value. Here are the rules for that int value:

• Return a negative value if this object is smaller than the other object
• Return 0 (zero) if this object is equal to the other object.
• Return a positive value if this object is larger than the other object.

There are a few more specific rules to obey in the implementation, but the above is the primary requirements. Check out the JavaDoc for the details.
Let's say you are sorting a List of String elements. To sort them, each string is compared to the others according to some sorting algorithm (not interesting here). Each string compares itself to another string by alphabetic comparison. So, if a string is less than another string by alphabetic comparison it will return a negative number from the compareTo() method.
When you implement the compareTo() method in your own classes you will have to decide how these objects should be compared to each other. For instance, Employee objects can be compared by their first name, last name, salary, start year or whatever else you think makes sense.

Sorting Objects Using a Comparator

Sometimes you may want to sort a list according to another order than their natural order. Perhaps the objects you are sorting do not even have a natural order. In that case you can use a Comparator instead. Here is how you sort a list using a Comparator:

List list = new ArrayList();

//add elements to the list

Comparator comparator = new SomeComparator();

Collections.sort(list, comparator);

Notice how the Collections.sort() method now takes a java.util.Comparator as parameter in addition to the List. This Comparator compares the elements in the list two by two. Here is how the Comparator interface looks:

public interface Comparator<T> {
    int compare(T object1, T object2);
}

The compare() method compares two objects to each other and should:

• Return a negative value if object1 is smaller than object2
• Return 0 (zero) if objec1 is equal to object2.
• Return a positive value if object1 is larger than object2.

There are a few more requirements to the implementation of the compare() method, but these are the primary requirements. Check out the JavaDoc for more specific details.
Here is an example Comparator that compares two fictive Employee objects:

public class MyComparator<Employee> implements Comparator<Employee> {

    public int compare(Employee emp1, Employee emp2){
       if(emp1.getSalary() <  emp2.getSalary()) return -1;
       if(emp1.getSalary() == emp2.getSalary()) return 0;
       return 1;
    }
}

A shorter way to write the comparison would be like this:

public class MyComparator<Employee> implements Comparator<Employee> {

    public int compare(Employee emp1, Employee emp2){
       return emp1.getSalary() - emp2.getSalary();
    }
}

By subtracting one salary from the other, the resulting value is automatically either negative, 0 or positive. Smart, right?
If you want to compare objects by more than one factor, start by comparing by the first factor (e.g first name). Then, if the first factors are equal, compare by the second factor (e.g. last name, or salary) etc