Formations — 1 037 leçons en français

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 compareTo dans 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.sort et Arrays.sort sur 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.

Lire l'explication détaillée et faire le quiz →

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.