Friday, April 18, 2014

Sort in Java

While analyzing source code of a large number of open source Java projects, I found Java developers frequently sort in two ways. One is using the sort() method of Collections or Arrays, and the other is using sorted data structures, such as TreeMap and TreeSet.
Using sort() Method
If it is a collection, use Collections.sort() method.
// Collections.sort
List<ObjectName> list = new ArrayList<ObjectName>();
Collections.sort(list, new Comparator<ObjectName>() {
 public int compare(ObjectName o1, ObjectName o2) {
  return o1.toString().compareTo(o2.toString());
 }
});
If it is an array, use Arrays.sort() method.
// Arrays.sort
ObjectName[] arr = new ObjectName[10];
Arrays.sort(arr, new Comparator<ObjectName>() {
 public int compare(ObjectName o1, ObjectName o2) {
  return o1.toString().compareTo(o2.toString());
 }
});
This is very convenient if a collection or an array is already set up.
Using Sorted Data Structures
If it is a list or set, use TreeSet to sort.
// TreeSet
Set<ObjectName> sortedSet = new TreeSet<ObjectName>(new Comparator<ObjectName>() {
 public int compare(ObjectName o1, ObjectName o2) {
  return o1.toString().compareTo(o2.toString());
 }
});
sortedSet.addAll(unsortedSet);
If it is a map, use TreeMap to sort. TreeMap is sorted by key.
// TreeMap - using String.CASE_INSENSITIVE_ORDER which is a Comparator that orders Strings by compareToIgnoreCase
Map<String, Integer> sortedMap = new TreeMap<String, Integer>(String.CASE_INSENSITIVE_ORDER);
sortedMap.putAll(unsortedMap);
//TreeMap - In general, defined comparator
Map<ObjectName, String> sortedMap = new TreeMap<ObjectName, String>(new Comparator<ObjectName>() {
 public int compare(ObjectName o1, ObjectName o2) {
  return o1.toString().compareTo(o2.toString());
 }
});
sortedMap.putAll(unsortedMap);
This approach is very useful, if you would do a lot of search operations for the collection. The sorted data structure will give time complexity of O(logn), which is lower than O(n).
Bad Practices
There are still bad practices, such as using self-defined sorting algorithm. Take the code below for example, not only the algorithm is not efficient, but also it is not readable. This happens a lot in different forms of variations.
double t;
for (int i = 0; i < 2; i++)
 for (int j = i + 1; j < 3; j++)
  if (r[j] < r[i]) {
   t = r[i];
   r[i] = r[j];
   r[j] = t;
  }

No comments:

Post a Comment