Accueil › Coding & algorithmique › Trier et comparer correctement
Trier et comparer correctement
Tri, recherche et Streamsintermediaire
Java offre deux façons de définir un ordre : Comparable (l'ordre naturel, dans la classe) et Comparator (un ordre externe, autant qu'on veut).
// Ordre naturel : un seul par classe
record Produit(String nom, BigDecimal prix) implements Comparable<Produit> {
@Override public int compareTo(Produit autre) { return nom.compareTo(autre.nom); }
}
// Ordres externes : composables
var parPrix = Comparator.comparing(Produit::prix);
var parPrixPuisNom = Comparator.comparing(Produit::prix).thenComparing(Produit::nom);
var parPrixDecroissant = Comparator.comparing(Produit::prix).reversed();
L'erreur classique : comparer par soustraction.
(a, b) -> a - b // ✗ déborde sur les grandes valeurs
Integer::compare // ✓
Comparator.comparingInt(Produit::stock) // ✓ et plus lisible
La stabilité permet de trier en plusieurs passes : trier par nom, puis par catégorie, donne des catégories dont le contenu reste trié par nom. Arrays.sort et Collections.sort sur des objets utilisent Timsort, qui est stable.
La complexité : O(n log n) pour tout tri par comparaison. Si les valeurs sont bornées — des notes de 0 à 20, des âges — un tri par comptage descend à O(n).
Les termes à connaître
- Comparable
L'ordre naturel d'un type, défini par
compareTodans la classe elle-même. Un seul ordre naturel par classe.- Comparator
Un ordre externe, défini à côté de la classe. On peut en avoir autant qu'on veut : par prix, par nom, par date.
- Comparator.comparing
La fabrique moderne :
Comparator.comparing(Produit::prix).thenComparing(Produit::nom).reversed(). Lisible, composable, sans risque de débordement.- Tri stable
Un tri qui conserve l'ordre relatif des éléments équivalents.
Collections.sortetArrays.sortsur des objets sont stables (Timsort) ; le tri de primitifs ne l'est pas (quicksort double pivot).- Contrat de comparaison
Un comparateur doit être cohérent : antisymétrique et transitif. Un comparateur incohérent peut faire lever
IllegalArgumentException: Comparison method violates its general contract!.- Tri par comptage
Quand les valeurs sont bornées et entières, ranger par valeur dans un tableau de compteurs donne un tri en O(n) — hors du cadre des tris par comparaison.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.