Sunday, February 10, 2013

Comparable vs. Comparator

At a first glance, these two interfaces seems to have no difference and it is easy to confuse both.

Comparable interface (java.lang)
This is used by the Collections.sort() and Arrays.sort(), so the elements in the collection needs to implement this interface, in order to be sorted.
This interface is frequently implemented in the API by String, Wrapper Classes, Date, Calendar...
This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method.

CompareTo returns an int with value:
negative    if this object < another object
zero          if this object == another object
positive     if this object > another object

class A implements Comparable<A>{
  String name=new String();

  public String getName(){ return name;}

  public int compareTo(A o) {
    return name.compareTo(o.getName());

class Test {
  public static void main ( String args[ ] ) {
    List<A> s= new ArrayList<A>();
    s.add(new A());
    s.add(new A());
    Collections.sort(s);  //if the collection does not implement Comparable, it will fail to compile in this line

Remember that:
When overriding equals(), the argument is of type Object
When overriding compareTo(), the argument should be of the type you're sorting (but Object is allowed if you don't use Generics).

Comparator interface (java.util)
There an overloaded version of the sort method that takes both a List and something called a Comparator.
Comparator gives you the ability to sort a given collection any number of different ways, so that we can sort instances of any class.

The class that implements Comparator is a separate class from the class whose instances you want to sort, this is used as an argument by the Collections.sort() and Arrays.sort()

class MySort implements Comparator<String>{
  public int compare(String one, String two) {
    return one.compareTo(two);

class Test {
  public static void main ( String args [ ] ) {
    List<String> s= new ArrayList<String>();
    Collections.sort(s,new MySort());

Searching Arrays and Collections with Comparable/Comparator
Searches are performed with the binarySearch() method.
The collection to be searched has to be sorted first, otherwise the result may become unpredictable (compiles, but the result may not be right).

If the collection was sorted with a natural order (elements implement Comparable), then a Comparator cannot be used to do the search (compiles, but the result may not be right).
Arrays.sort(array) must be used with

If the collection was sorted with a Comparator, then it must be searched with a Comparator  (compiles, but the result may not be right).
Arrays.sort(array,someComparatorInstance) must be used with Arrays.binarySearch(array,elementToSearch,someComparatorInstance);

Successful searches returns an int index of the element being searched.
Unsuccessful searches returns a negative int index of the insertion point, that would be used to keep the collection properly sorted. The result formula for unsuccessful searched is (- (insertion point) -1 ).

No comments:

Post a Comment