Trier les collections Java

Trier une collection Java se fait via trois points d'entrée idiomatiques : Collections.sort(list), list.sort(comparator) et stream.sorted(). Tous trois partagent le même algorithme sous-jacent — un mergesort stable et adaptatif (variante TimSort) avec un pire cas en O(n log n) — et dépendent soit d'un type d'élément Comparable, soit d'un Comparator que vous fournissez. Les différences portent sur où le résultat se trouve et comment le code s'écrit.

Ce chapitre traite des listes. Les ensembles et les maps ont leurs propres mécanismes pour rester triés (TreeSet, TreeMap) — ils trient à l'insertion, pas après coup. Si vous avez un HashSet à trier, le schéma classique est new ArrayList<>(set) suivi d'un tri.

Les trois points d'entrée

Collections.sort(list) — l'original

Collections.sort(list);                  // natural ordering — list element type must implement Comparable
Collections.sort(list, comparator);       // explicit comparator

En place. Stable. Retourne void. Antérieur à Java 8, il reste courant car il se lit clairement et précède les alternatives. En interne, il délègue à list.sort sur les JDK modernes.

list.sort(comparator) — la méthode d'instance moderne

list.sort(null);                          // natural ordering — null means "use Comparable"
list.sort(comparator);

Ajouté en Java 8 directement sur List<E>. Même sémantique que Collections.sort — en place, stable, retourne void. La forme d'instance permet à une implémentation de liste de surcharger l'algorithme si elle peut faire mieux (par exemple, LinkedList ne le fait pas, mais une liste personnalisée pourrait le faire).

Utilisez list.sort pour le nouveau code. C'est plus court, se lit mieux avec des références de méthode et n'exige pas d'importer Collections.

stream.sorted() — quand vous voulez une nouvelle séquence

List<Person> sorted = people.stream()
                            .sorted(Comparator.comparingInt(Person::age))
                            .toList();

Retourne un nouveau flux trié — l'entrée reste intacte. Utilisez ceci quand :

• L'entrée est immuable (List.of(...)) et list.sort lèverait une exception.
• Vous construisez un pipeline de toute façon (map, filter, puis tri).
• Vous ne souhaitez pas modifier la liste source.

Le coût est une allocation supplémentaire pour le résultat trié. Pour les listes courtes, c'est négligeable ; pour une liste d'un million d'éléments, un Collections.sort modifiant en place est moins coûteux qu'un stream().sorted().toList() qui copie tout.

Ordre naturel vs comparateur

Collections.sort(list) et list.sort(null) utilisent tous deux l'ordre naturel du type d'élément, défini par son implémentation de Comparable :

List<String> names = new ArrayList<>(List.of("carol", "alice", "bob"));
names.sort(null);                        // [alice, bob, carol]

Si le type d'élément n'implémente pas Comparable, vous obtiendrez une ClassCastException à l'exécution — pas une erreur de compilation, car le cast se produit à l'intérieur du tri. Passez un Comparator explicitement pour corriger cela :

List<Person> people = new ArrayList<>(...);
people.sort(Comparator.comparing(Person::name));

Tout Comparator du chapitre précédent s'applique — clé unique, clés chaînées, inversé, tolérant les null, etc.

Tri stable : les éléments égaux conservent leur ordre

TimSort est stable : si deux éléments sont égaux selon le comparateur, celui qui apparaissait en premier dans l'entrée apparaît toujours en premier dans la sortie. C'est ce qui permet au tri multi-clé de fonctionner comme des passes successives sur clé unique :

people.sort(Comparator.comparing(Person::lastName));     // first pass
people.sort(Comparator.comparingInt(Person::age));        // second pass — primary key wins, ties broken by previous order

Après les deux passes, la liste est triée par age en priorité et par lastName au sein de chaque groupe d'âge. Trier dans l'ordre inverse de priorité — clé secondaire en premier, clé primaire en dernier — est l'astuce qui rend le tri multi-passe fonctionnel. La plupart du temps, vous écririez plutôt le comparateur chaîné du chapitre précédent ; c'est l'alternative historique.

Listes modifiables vs non modifiables

List.of(...), Collections.unmodifiableList(...) et Arrays.asList(array) retournent tous des listes que vous ne pouvez pas trier en place. list.sort(...) appelle list.set(i, x) en interne, et les listes immuables lèvent une UnsupportedOperationException à ce niveau.

Deux solutions :

List<String> sorted = original.stream().sorted().toList();   // new immutable, sorted list
List<String> copy   = new ArrayList<>(original); copy.sort(null);

Arrays.asList(...) est un cas particulier : la liste est de taille fixe mais les emplacements sont modifiables, donc sort fonctionne. add/remove ne fonctionnent pas.

Listes primitives et le coût de l'autoboxing

List<Integer> encapsule chaque valeur. Trier un million d'Integer est beaucoup plus lent que trier un int[]. Si les données sont primitives, préférez :

int[] data = ...;
Arrays.sort(data);                       // primitive sort: cache-friendly, no boxing

…puis convertissez en liste si vous en avez besoin plus tard. Le même schéma s'applique à long[], double[], char[]. Si vous triez par une clé primitive sur des objets, utilisez Comparator.comparingInt, comparingLong, comparingDouble pour éviter l'autoboxing dans le comparateur :

people.sort(Comparator.comparingInt(Person::age));     // unboxed key extraction

Collections.sort modifie en place ; parfois vous voulez une copie

Si vous souhaitez un résultat trié sans modifier la source :

List<String> sortedCopy = new ArrayList<>(source);
sortedCopy.sort(null);

…ou la forme avec stream :

List<String> sortedCopy = source.stream().sorted().toList();

Les deux fonctionnent. La première approche nécessite deux lignes et n'a aucune surcharge de pipeline. La seconde est une expression unique. Choisissez celle qui s'intègre le mieux au code environnant.

Trier une Map par valeur

Les maps n'ont pas de méthode sort — il n'y a pas de « position » dans une Map. L'idiome consiste à trier l'ensemble des entrées dans une List puis à l'itérer :

List<Map.Entry<String, Integer>> byCount = scores.entrySet().stream()
    .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
    .toList();

Si vous avez besoin que le résultat soit une map qui itère dans cet ordre, collectez dans une LinkedHashMap — son ordre d'insertion est son ordre d'itération :

LinkedHashMap<String, Integer> ordered = scores.entrySet().stream()
    .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
    .collect(Collectors.toMap(
        Map.Entry::getKey, Map.Entry::getValue,
        (a, b) -> a, LinkedHashMap::new));

La surcharge à quatre arguments de toMap vous permet de choisir l'implémentation de la map. Ne la sautez pas — la valeur par défaut est HashMap, ce qui détruit l'ordre que vous venez d'imposer.

Un exemple complet : tri en place, tri par stream, comparateur chaîné, tri d'une map

Le programme ci-dessous trie une liste en place, construit une copie triée avec stream().sorted(), applique un comparateur chaîné avec une clé secondaire inversée, puis trie une map par valeur dans une LinkedHashMap qui itère dans l'ordre trié.

Ce que l'exécution nous enseigne :

• Le tri en place a utilisé le comparateur chaîné et produit un résultat trié par âge croissant avec des tie-breakers par salaire décroissant en un seul appel. Aucune deuxième passe nécessaire.
• La forme avec stream a retourné une nouvelle liste triée et laissé la source List.of intacte. C'est le bon schéma quand l'entrée est immuable ou partagée.
• Appeler sort sur une liste immuable a levé une UnsupportedOperationException. Le tri est en place, et « en place » exige la mutabilité.
• Le classement de la map a abouti dans une LinkedHashMap, donc son itération correspond à l'ordre de tri. Si nous avions utilisé le toMap à trois arguments, le résultat aurait été une HashMap et l'ordre aurait été perdu.

La suite

Vous pouvez désormais ordonner n'importe quelle liste et produire une copie triée sans modifier la source. La recherche est la prochaine opération — trouver un élément par prédicat, par égalité, ou par recherche binaire sur une liste déjà triée. Le chapitre suivant est Rechercher dans les collections Java.

Pratique