Ordinare le Java Collections

Ordinare una collection Java è un'operazione con tre punti di ingresso idiomatici: Collections.sort(list), list.sort(comparator) e stream.sorted(). Tutti e tre condividono lo stesso algoritmo sottostante — un mergesort stabile e adattivo (variante TimSort) con caso peggiore O(n log n) — e la stessa dipendenza da un tipo di elemento Comparable o da un Comparator fornito dall'utente. Le differenze stanno in dove si trova il risultato e in come appare il punto di chiamata.

Questo capitolo riguarda le liste. Set e map hanno i propri modi per mantenersi ordinati (TreeSet, TreeMap) — ordinano all'inserimento, non a posteriori. Se hai un HashSet che vuoi ordinare, il pattern standard è new ArrayList<>(set) seguito da un ordinamento.

I tre punti di ingresso

Collections.sort(list) — l'originale

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

In place. Stabile. Restituisce void. Precede Java 8 ed è ancora comune perché è leggibile e precede le alternative. Internamente delega a list.sort nei JDK moderni.

list.sort(comparator) — il metodo d'istanza moderno

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

Aggiunto in Java 8 direttamente su List<E>. Stessa semantica di Collections.sort — in place, stabile, restituisce void. La forma d'istanza consente a un'implementazione di lista di sovrascrivere l'algoritmo se può fare meglio (ad esempio LinkedList non lo fa, ma una lista personalizzata potrebbe).

Usa list.sort per il nuovo codice. È più breve, si legge meglio con i riferimenti a metodo e non richiede l'importazione di Collections.

stream.sorted() — quando vuoi una nuova sequenza

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

Restituisce un nuovo stream ordinato — l'input rimane invariato. Usalo quando:

• L'input è immutabile (List.of(...)) e list.sort lancerebbe un'eccezione.
• Stai comunque costruendo una pipeline (map, filter, poi sort).
• Non vuoi mutare la lista sorgente.

Il costo è un'allocazione aggiuntiva del risultato ordinato. Per liste brevi è trascurabile; per una lista di un milione di elementi, un Collections.sort che muta in place è più economico di un stream().sorted().toList() che copia l'intero contenuto.

Ordinamento naturale vs comparatore

Sia Collections.sort(list) che list.sort(null) utilizzano l'ordinamento naturale del tipo di elemento, definito dalla sua implementazione di Comparable:

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

Se il tipo di elemento non implementa Comparable, si vedrà una ClassCastException a runtime — non un errore di compilazione, perché il cast avviene all'interno dell'ordinamento. Passa un Comparator esplicitamente per risolvere il problema:

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

Qualsiasi Comparator del capitolo precedente si applica — singola chiave, chiavi concatenate, invertito, null-safe, e così via.

Ordinamento stabile: gli elementi uguali mantengono il loro ordine

TimSort è stabile: se due elementi sono uguali sotto il comparatore, quello che veniva prima nell'input viene ancora prima nell'output. Questo è ciò che permette all'ordinamento multi-chiave di funzionare come passaggi singoli composti:

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

Dopo entrambi i passaggi, la lista è ordinata per age come chiave primaria e per lastName all'interno di ogni gruppo d'età. Ordinare in ordine inverso di priorità — prima la chiave secondaria, ultima la chiave primaria — è il trucco che fa funzionare l'ordinamento multi-passaggio. La maggior parte delle volte si scriverebbe invece il comparatore concatenato del capitolo precedente; questa è l'alternativa legacy.

Liste modificabili vs non modificabili

List.of(...), Collections.unmodifiableList(...) e Arrays.asList(array) restituiscono tutte liste che non è possibile ordinare in place. list.sort(...) chiama list.set(i, x) internamente, e le liste immutabili lanciano UnsupportedOperationException da quel punto.

Due soluzioni:

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

Arrays.asList(...) è un caso speciale: la lista è di dimensione fissa ma i slot sono modificabili, quindi sort funziona. add/remove non funzionano.

Liste primitive e il costo del boxing

List<Integer> esegue il boxing di ogni valore. Ordinare un milione di Integer è molto più lento che ordinare un int[]. Se i dati sono primitivi, preferisci:

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

…poi converti in una lista se ne hai bisogno in seguito. Lo stesso pattern si applica a long[], double[], char[]. Se stai ordinando per una chiave primitiva su oggetti, usa Comparator.comparingInt, comparingLong, comparingDouble per evitare il boxing all'interno del comparatore:

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

Collections.sort è in place; a volte vuoi una copia

Se vuoi un risultato ordinato senza mutare la sorgente:

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

…oppure la forma con stream:

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

Entrambi funzionano. Il primo è due righe senza overhead di pipeline. Il secondo è un'unica espressione. Scegli quello che si adatta meglio al codice circostante.

Ordinare una Map per valore

Le map non hanno un metodo sort — non esiste una "posizione" su una Map. Il pattern idiomatico è ordinare l'insieme di entry in una List e poi iterarla:

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

Se hai bisogno che il risultato sia una map che itera in quell'ordine, raccogli in una LinkedHashMap — il suo ordine di inserimento è il suo ordine di iterazione:

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

L'overload toMap a quattro argomenti consente di scegliere l'implementazione della map. Non ometterlo — il default è HashMap, che distrugge l'ordine appena imposto.

Un esempio pratico: sort in-place, stream sort, comparatore concatenato, ordinamento di una map

Il programma seguente ordina una lista in place, costruisce una copia ordinata con stream().sorted(), applica un comparatore concatenato con una chiave secondaria invertita, poi ordina una map per valore in una LinkedHashMap che itera nell'ordine ordinato.

Cosa ricavare dall'esecuzione:

• L'ordinamento in-place ha utilizzato il comparatore concatenato e ha prodotto età crescente con stipendio decrescente come tie-breaker in una sola chiamata. Nessun secondo passaggio necessario.
• La forma con stream ha restituito una nuova lista ordinata e ha lasciato la sorgente List.of invariata. Questo è il pattern corretto quando l'input è immutabile o condiviso.
• Chiamare sort su una lista immutabile ha lanciato UnsupportedOperationException. L'ordinamento è in place, e "in place" richiede mutabilità.
• Il ranking della map è finito in una LinkedHashMap, quindi la sua iterazione corrisponde all'ordine di ordinamento. Se avessimo usato il toMap a tre argomenti, il risultato sarebbe stato una HashMap e l'ordine sarebbe andato perso.

Cosa c'è dopo

Ora puoi ordinare qualsiasi lista e puoi produrre una copia ordinata senza mutare la sorgente. La ricerca è la prossima operazione — trovare un elemento per predicato, per uguaglianza o per ricerca binaria su una lista già ordinata. Il prossimo capitolo è Ricerca nelle Java Collections.

Pratica