Ordinare gli array in Java

L'ordinamento è una delle operazioni che utilizzerai continuamente, e la libreria standard di Java lo rende un'operazione in una riga — la maggior parte delle volte. Il problema è che il tipo di elemento fa la differenza: i primitivi si ordinano in un modo, gli oggetti in un altro, e "voglio l'ordine decrescente" o "ordina per un campo" richiede un Comparator. Questo capitolo affronta tutto ciò.

Il metodo principale è Arrays.sort. Ordina in-place — modifica l'array che gli passi. Se vuoi conservare l'originale, copialo prima.

Ordinare i primitivi

Per int[], long[], double[], char[], ecc., una sola chiamata è sufficiente:

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]

L'ordinamento dei primitivi è sempre crescente. Non esiste un overload con Comparator — i primitivi non possono essere confrontati da una funzione arbitraria come gli oggetti.

Per ordinare in modo decrescente, il trucco è trasformare in Integer[] e fornire un comparatore, oppure ordinare in modo crescente e invertire manualmente:

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

Ordinare un intervallo

Passa from (incluso) e to (escluso) per ordinare solo una parte dell'array:

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

Gli elementi al di fuori dell'intervallo rimangono al loro posto.

Ordinare array di oggetti (ordine naturale)

Per un array di oggetti la cui classe implementa Comparable<T> — String, i wrapper numerici boxati, LocalDate, qualsiasi cosa con un ordine "naturale" — chiama Arrays.sort direttamente:

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

Se la classe non implementa Comparable, questo genera un ClassCastException a runtime. La soluzione è fornire un Comparator.

Ordinare con un Comparator

Un Comparator<T> è una funzione che, dati due T, restituisce un numero negativo, zero o un numero positivo per indicare "il primo è minore", "sono uguali", "il primo è maggiore". Il modo più pulito per crearne uno è con 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));

La catena Comparator.comparing(...).reversed() e .thenComparing(...) è il modo idiomatico per comporre gli ordinamenti. Non hai quasi mai bisogno di scrivere a mano una classe comparatore. Per un'analisi più approfondita della differenza tra l'ordine naturale di una classe e un Comparator esterno, vedi Comparable vs Comparator.

Gestire gli elementi null

Un comparatore normale genera NullPointerException se l'array contiene un null. Avvolgilo con Comparator.nullsFirst o Comparator.nullsLast per spostare i null a un estremo:

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

Ordinare primitivi boxati

Integer[], Double[], ecc. sono array di oggetti — quindi tutta la meccanica dei Comparator è disponibile:

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

Se hai bisogno dell'ordine decrescente per un array di primitivi, il boxing è la soluzione più pulita — a patto che l'array non sia enorme, il costo è accettabile.

Stabilità

La stabilità dell'ordinamento significa che gli elementi uguali mantengono il loro ordine relativo originale. L'ordinamento degli oggetti in Java è stabile: se due Player hanno lo stesso punteggio, quello che veniva prima rimane prima. L'ordinamento dei primitivi non è garantito stabile, ma poiché i primitivi non hanno identità oltre al loro valore, non si può notare la differenza.

Questo è importante quando si concatenano gli ordinamenti — ad esempio, ordina per punteggio, poi per nome. Con un ordinamento stabile, il secondo passaggio preserva il primo ordinamento dove la nuova chiave è uguale. Con thenComparing, si compongono entrambe le chiavi in un unico comparatore e si evita il problema, il che di solito è l'approccio più pulito.

parallelSort

Per array molto grandi, Arrays.parallelSort distribuisce il lavoro su più thread:

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

Stessa API, stessa semantica in-place. C'è un overhead nella configurazione dei thread, quindi per array piccoli un sort normale è più veloce. Il punto di incrocio è intorno alle decine di migliaia di elementi; al di sotto di quel valore, non conviene.

Se i tuoi dati si trovano in una List anziché in un array, l'equivalente è Collections.sort o list.sort(...) — le stesse regole sui comparatori si applicano. Vedi come ordinare un ArrayList.

Un esempio pratico

Cosa c'è dopo

Hai ora visto il lato lettura-e-trasformazione degli array. L'ultimo capitolo di questa parte tratta la copia degli array — il modo corretto per duplicare, affettare e ridimensionare un array esistente senza intrecciare i due con riferimenti condivisi.

Pratica