Trier des tableaux en Java

Le tri est l'une de ces opérations que vous utiliserez constamment, et la bibliothèque standard de Java en fait une opération en une ligne — la plupart du temps. La subtilité réside dans le type d'élément : les primitives se trient d'une manière, les objets d'une autre, et « je veux un ordre décroissant » ou « trier par un champ » nécessite un Comparator. Ce chapitre couvre tout cela.

La méthode centrale est Arrays.sort. Elle trie sur place — elle modifie le tableau que vous lui passez. Si vous souhaitez conserver l'original, copiez-le d'abord.

Trier des primitives

Pour int[], long[], double[], char[], etc., un seul appel suffit :

import java.util.Arrays;

int[] data = {3, 1, 4, 1, 5, 9, 2, 6};
Arrays.sort(data);
System.out.println(Arrays.toString(data));   // [1, 1, 2, 3, 4, 5, 6, 9]

Le tri de primitives est toujours croissant. Il n'existe pas de surcharge avec Comparator — les primitives ne peuvent pas être comparées par une fonction arbitraire comme les objets.

Pour trier en ordre décroissant, la technique consiste à boxer vers Integer[] et fournir un comparateur, ou trier en ordre croissant et inverser manuellement :

int[] data = {3, 1, 4};
Arrays.sort(data);
// reverse in place
for (int i = 0, j = data.length - 1; i < j; i++, j--) {
  int tmp = data[i]; data[i] = data[j]; data[j] = tmp;
}

Trier une plage

Passez from (inclus) et to (exclusif) pour trier uniquement une partie du tableau :

int[] data = {9, 8, 7, 6, 5, 4, 3, 2, 1};
Arrays.sort(data, 2, 6);
// {9, 8, 4, 5, 6, 7, 3, 2, 1} — only positions 2..5 sorted

Les éléments en dehors de la plage restent en place.

Trier des tableaux d'objets (ordre naturel)

Pour un tableau d'objets dont la classe implémente Comparable<T> — String, les wrappers numériques boxés, LocalDate, tout ce qui possède un ordre « naturel » — appelez Arrays.sort directement :

String[] words = {"banana", "apple", "cherry"};
Arrays.sort(words);
// {"apple", "banana", "cherry"} — alphabetical

Si la classe n'implémente pas Comparable, cela lève une ClassCastException à l'exécution. La solution est de fournir un Comparator.

Trier avec un Comparator

Un Comparator<T> est une fonction qui, étant donné deux T, retourne un nombre négatif, zéro ou un nombre positif pour indiquer « le premier est plus petit », « égaux », « le premier est plus grand ». La façon la plus propre de le construire est avec Comparator.comparing :

record Player(String name, int score) {}

Player[] players = {
  new Player("Ada", 1500),
  new Player("Linus", 1800),
  new Player("Grace", 1650)
};

// sort by score, ascending
Arrays.sort(players, Comparator.comparing(Player::score));

// sort by score, descending
Arrays.sort(players, Comparator.comparing(Player::score).reversed());

// sort by name (case-insensitive), then by score as tiebreaker
Arrays.sort(players,
  Comparator.comparing(Player::name, String.CASE_INSENSITIVE_ORDER)
            .thenComparing(Player::score));

L'enchaînement Comparator.comparing(...).reversed() et .thenComparing(...) est la manière idiomatique de composer des ordres de tri. Vous n'avez presque jamais besoin d'écrire une classe de comparateur à la main. Pour approfondir la différence entre l'ordre naturel d'une classe et un Comparator externe, consultez Comparable vs Comparator.

Gérer les éléments null

Un comparateur simple lève une NullPointerException si le tableau contient un null. Enveloppez-le avec Comparator.nullsFirst ou Comparator.nullsLast pour repousser les nulls à l'une ou l'autre extrémité :

String[] words = {"banana", null, "apple"};
Arrays.sort(words, Comparator.nullsFirst(Comparator.naturalOrder()));
// {null, "apple", "banana"}

Trier des primitives boxées

Integer[], Double[], etc. sont des tableaux d'objets — tout le mécanisme de Comparator est donc disponible :

Integer[] nums = {3, 1, 4, 1, 5};
Arrays.sort(nums, Comparator.reverseOrder());
// {5, 4, 3, 1, 1}

Si vous avez besoin d'un ordre décroissant pour un tableau de primitives, le boxing est la solution la plus propre — en supposant que le tableau n'est pas énorme, le coût est acceptable.

Stabilité

La stabilité du tri signifie que les éléments égaux conservent leur ordre relatif d'origine. Le tri d'objets de Java est stable : si deux Player ont le même score, celui qui est venu en premier reste en premier. Le tri de primitives n'est pas garanti stable, mais comme les primitives ne portent aucune identité au-delà de leur valeur, cela n'est pas perceptible.

Cela est important lorsque vous enchaînez des tris — par exemple, trier par score, puis par nom. Avec un tri stable, le second passage préserve le premier ordre là où la nouvelle clé est égale. Avec thenComparing, vous composez les deux clés en un seul comparateur et contournez la question, ce qui est généralement l'approche la plus propre.

parallelSort

Pour les très grands tableaux, Arrays.parallelSort distribue le travail sur plusieurs threads :

int[] huge = new int[10_000_000];
// ... fill huge ...
Arrays.parallelSort(huge);

Même API, mêmes sémantiques sur place. Il y a un coût de démarrage pour configurer les threads, donc pour les petits tableaux un simple sort est plus rapide. Le point de bascule se situe autour de dizaines de milliers d'éléments ; en dessous de ce seuil, ne vous en préoccupez pas.

Si vos données sont dans une List plutôt que dans un tableau, l'équivalent est Collections.sort ou list.sort(...) — les mêmes règles de comparateur s'appliquent. Voir comment trier une ArrayList.

Un exemple pratique

Prochaine étape

Vous avez maintenant vu le côté lecture et transformation des tableaux. Le dernier chapitre de cette partie couvre la copie de tableaux — la bonne façon de dupliquer, découper et redimensionner un tableau existant sans les enchevêtrer avec des références partagées.

Exercices