How to do sorting correctly in Java

Analyzing the source code of many opensource Java projects, I found that most developers implement sorting in only two different ways. One of them is based on the use of the sort()class method Collectionsor Arrays, and the other is based on the use of self-sorting data structures such as TreeMapand TreeSet.

Using the sort() method

If you need to sort a collection, then use the Collections.sort().

// 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 you need to sort an array, use the Arrays.sort().

// 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());
	}
});

The method sort()is very convenient when the collection or array is already filled with values.

Using self-sorting data structures

If you need to sort a list ( List) or set ( Set), use a TreeSetsorting structure.

// 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 you need to sort a dictionary ( Map), use a TreeMapsorting structure. TreeMapsorted by key ( key).

// TreeMap – использующий String ключи и компаратор (Comparator) CASE_INSENSITIVE_ORDER,
// упорядочивающий строки (String) методом compareToIgnoreCase
Map<String, Integer> sortedMap = new TreeMap<String, Integer>(String.CASE_INSENSITIVE_ORDER);
sortedMap.putAll(unsortedMap);

//TreeMap – общий случай, компаратор указывается вручную
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);

The above approach is very useful in cases where you need to perform a large number of searches for elements in a collection. Self-sorting data structures have an efficiency O(log(n))that is better than O(n). This means that when the amount of data in the collection doubles, the search time does not double, but increases by a constant amount .

Bad approach to sorting problem

You can still find examples where programmers independently describe sorting algorithms. Consider the sorting code presented below (sorting a double array in ascending order ). This code is not only inefficient, but also unreadable. And there are many such examples.

double t;
for (int i = 0; i < N; i++)
	for (int j = i + 1; j < N; j++)
		if (r[j] < r[i]) {
			t = r[i];
			r[i] = r[j];
			r[j] = t;
		}