Comment effectuer un tri correctement en Java

En analysant le code source de nombreux projets Java open source, j'ai constaté que la plupart des développeurs implémentent le tri de deux manières différentes seulement. L'un d'eux est basé sur l'utilisation de la méthode sort()de classe Collectionsou Arrays, et l'autre est basé sur l'utilisation de structures de données à tri automatique telles que TreeMapet TreeSet.

Utilisation de la méthode sort()

Si vous devez trier une collection, utilisez le 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());
	}
});

Si vous devez trier un tableau, utilisez le 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());
	}
});

La méthode sort()est très pratique lorsque la collection ou le tableau est déjà rempli de valeurs.

Utiliser des structures de données à tri automatique

Si vous devez trier une liste ( List) ou un ensemble ( Set), utilisez une TreeSetstructure de tri.

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

Si vous devez trier un dictionnaire ( Map), utilisez une TreeMapstructure de tri. TreeMaptriés par clé ( 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);

L'approche ci-dessus est très utile dans les cas où vous devez effectuer un grand nombre de recherches d'éléments dans une collection. Les structures de données à tri automatique ont une efficacité O(log(n))meilleure que O(n). Cela signifie que lorsque la quantité de données dans la collection double, le temps de recherche ne double pas, mais augmente d'une quantité constante .

Mauvaise approche du problème de tri

Vous pouvez toujours trouver des exemples dans lesquels des programmeurs décrivent indépendamment des algorithmes de tri. Considérez le code de tri présenté ci-dessous (tri d'un double tableau par ordre croissant ). Ce code est non seulement inefficace, mais aussi illisible. Et il existe de nombreux exemples de ce type.

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;
		}