Saturday, August 8, 2009

how to sort using comparators

Although Collections class' sort method is quite handy, there will be times you'll need to do tricky stuff while sorting. But you can still use this static method with your Comparator that'll ensure the desired sorting behavior.

Lets quote the definition of Comparator class:
A comparison function, which imposes a total ordering on some collection of objects. Comparators can be passed to a sort method (such as Collections.sort or Arrays.sort) to allow precise control over the sort order


Assume that we want to sort a List of floats by considering only the part after the dot. So we will consider 63 of 3.63 and 72 of 2.72 and their increasing order will be {3.63, 2.72} because 63 < 72. The code of the Comparator is below.


// we use generics (Float here) for avoiding a downcast
class FloatComparator implements Comparator < Float >{

public int compare(Float f1, Float f2) {
// for instance, 323.432 - 323 ~= 0.432
Float f1_ = f1 - f1.intValue(); /* intValue() returns the floor integer (not the closest integer) */
Float f2_ = f2 - f2.intValue();
/* after stripping the float from the integer part we use float's compareTo function compare the remaining part of the number */
return f1_.compareTo(f2_);
}


}




We implemented the Comparator interface in the class. In public int compare method we first remove the integer part of the float and then compare the rest. If you must do more trickier stuff you have to consider few things. I'm quoting from Sun's Comparator documentation:

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

Finally, the implementor must ensure that compare(x, y)==0 implies that
sgn(compare(x, z))==sgn(compare(y, z)) for all z.



As we use the compareTo method of Float, we don't have to think about the above cases. They are already handled.

Lets see our FloatComparator in action.


public class SortingWithComparator {

public static void main(String[] args) {
List < Float > numberList = new ArrayList < Float > ();
numberList.add(323.432F);
numberList.add(34.234F);
numberList.add(-81.01F);
numberList.add(49.736F);

for(Float number : numberList)
System.out.println(number);

Collections.sort(numberList, new FloatComparator()); /* sort numberList using the FloatComparator */
System.out.println("------- after sorting takes place -----");

for(Float number : numberList)
System.out.println(number);

}
}


The output is:


323.432
34.234
-81.01
49.736
------- after sorting takes place -----
-81.01
34.234
323.432
49.736

No comments:

Post a Comment