Java Sorting Collections
Jakob Jenkov |
You can sort a Java List collections using the java.util.Collections.sort() method.
You can sort these two types of List's.
- List
- 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.
See the Java Comparable tutorial for more information about the Comparable interface.
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. See the Java Comparator tutorial for
more information about the Comparator interface.
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.
| Tweet | |
Jakob Jenkov | |
