Java Collections sortieren

Das Sortieren einer Java-Collection ist eine Operation mit drei idiomatischen Einstiegspunkten: Collections.sort(list), list.sort(comparator) und stream.sorted(). Alle drei basieren auf demselben zugrunde liegenden Algorithmus — einem stabilen, adaptiven Mergesort (TimSort-Variante) mit O(n log n) im schlechtesten Fall — und derselben Abhängigkeit von entweder einem Comparable-Elementtyp oder einem Comparator, den Sie bereitstellen. Die Unterschiede liegen darin, wo das Ergebnis liegt und wie die Aufrufstelle aussieht.

Dieses Kapitel behandelt Listen. Sets und Maps haben ihre eigenen Möglichkeiten, sortiert zu bleiben (TreeSet, TreeMap) — sie sortieren beim Einfügen, nicht im Nachhinein. Wenn Sie ein HashSet sortiert haben möchten, ist das Standardmuster new ArrayList<>(set) gefolgt von einem Sort.

Die drei Einstiegspunkte

Collections.sort(list) — das Original

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

In Place. Stabil. Gibt void zurück. Stammt aus der Zeit vor Java 8 und ist nach wie vor verbreitet, weil es klar lesbar ist und vor den Alternativen existierte. Intern delegiert es auf modernen JDKs an list.sort.

list.sort(comparator) — die moderne Instanzmethode

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

In Java 8 direkt auf List<E> hinzugefügt. Gleiche Semantik wie Collections.sort — in place, stabil, gibt void zurück. Die Instanzform erlaubt einer List-Implementierung, den Algorithmus zu überschreiben, wenn sie es besser kann (z. B. tut LinkedList das nicht, aber eine benutzerdefinierte Liste könnte es).

Verwenden Sie list.sort für neuen Code. Es ist kürzer, liest sich besser mit Methodenreferenzen und erfordert keinen Import von Collections.

stream.sorted() — wenn Sie eine neue Sequenz möchten

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

Gibt einen neuen sortierten Stream zurück — die Eingabe bleibt unverändert. Verwenden Sie dies, wenn:

• Die Eingabe unveränderlich ist (List.of(...)) und list.sort eine Exception werfen würde.
• Sie ohnehin eine Pipeline aufbauen (map, filter, dann sort).
• Sie die Quellliste nicht verändern möchten.

Der Nachteil ist eine zusätzliche Allokation für das sortierte Ergebnis. Bei kurzen Listen ist das vernachlässigbar; bei einer Million-Elemente-Liste ist ein Collections.sort mit In-Place-Mutation günstiger als ein stream().sorted().toList(), das alles kopiert.

Natürliche Reihenfolge vs. Comparator

Sowohl Collections.sort(list) als auch list.sort(null) verwenden die natürliche Reihenfolge des Elementtyps, die durch seine Comparable-Implementierung definiert wird:

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

Wenn der Elementtyp Comparable nicht implementiert, erhalten Sie zur Laufzeit eine ClassCastException — keinen Compilerfehler, da der Cast innerhalb des Sorts erfolgt. Übergeben Sie einen Comparator explizit, um das zu beheben:

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

Jeder Comparator aus dem vorherigen Kapitel ist anwendbar — einzelner Schlüssel, verkettete Schlüssel, umgekehrt, null-sicher und so weiter.

Stabiler Sort: gleiche Elemente behalten ihre Reihenfolge

TimSort ist stabil: Wenn zwei Elemente unter dem Comparator gleich sind, kommt das, das in der Eingabe zuerst kam, auch in der Ausgabe zuerst. Das ermöglicht mehrstufiges Sortieren als zusammengesetzte Einzelschlüssel-Durchläufe:

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

Nach beiden Durchläufen ist die Liste primär nach age und innerhalb jeder Altersgruppe nach lastName sortiert. Das Sortieren in umgekehrter Prioritätsreihenfolge — sekundärer Schlüssel zuerst, primärer Schlüssel zuletzt — ist der Trick, der Mehrfach-Durchlauf-Sortierung ermöglicht. In den meisten Fällen würden Sie stattdessen den verketteten Comparator aus dem vorherigen Kapitel schreiben; dies ist die veraltete Alternative.

Veränderliche vs. unveränderliche Listen

List.of(...), Collections.unmodifiableList(...) und Arrays.asList(array) liefern Listen, die Sie nicht in place sortieren können. list.sort(...) ruft intern list.set(i, x) auf, und unveränderliche Listen werfen eine UnsupportedOperationException dabei.

Zwei Lösungen:

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

Arrays.asList(...) ist ein Sonderfall: Die Liste hat eine feste Größe, aber die Slots sind veränderlich, daher funktioniert sort. add/remove hingegen nicht.

Primitive Listen und der Boxing-Aufwand

List<Integer> boxed jeden Wert. Das Sortieren einer Million Integer-Objekte ist viel langsamer als das Sortieren eines int[]. Wenn die Daten primitiv sind, bevorzugen Sie:

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

…und konvertieren Sie dann bei Bedarf in eine Liste. Dasselbe Muster gilt für long[], double[], char[]. Wenn Sie nach einem primitiven Schlüssel auf Objekten sortieren, verwenden Sie Comparator.comparingInt, comparingLong, comparingDouble, um Boxing im Comparator zu vermeiden:

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

Collections.sort ist in place; manchmal möchten Sie eine Kopie

Wenn Sie ein sortiertes Ergebnis möchten, ohne die Quelle zu verändern:

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

…oder die Stream-Variante:

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

Beide funktionieren. Die erste Variante ist zwei Zeilen ohne Pipeline-Overhead. Die zweite ist ein Ausdruck. Wählen Sie, was besser zum umgebenden Code passt.

Eine Map nach Wert sortieren

Maps haben keine sort-Methode — es gibt keine "Position" auf einer Map. Das Idiom besteht darin, die Entry-Menge in eine List zu sortieren und diese dann zu iterieren:

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

Wenn das Ergebnis eine Map sein soll, die in dieser Reihenfolge iteriert, sammeln Sie in eine LinkedHashMap — ihre Einfügereihenfolge ist ihre Iterationsreihenfolge:

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

Die vierargumentige toMap-Überladung erlaubt es Ihnen, die Map-Implementierung zu wählen. Lassen Sie das nicht aus — der Standard ist HashMap, der die gerade aufgezwungene Reihenfolge zerstört.

Ein durchgearbeitetes Beispiel: In-Place-Sort, Stream-Sort, verketteter Comparator, Map nach Wert sortieren

Das folgende Programm sortiert eine Liste in place, erstellt eine sortierte Kopie mit stream().sorted(), wendet einen verketteten Comparator mit einem umgekehrten sekundären Schlüssel an und sortiert dann eine Map nach Wert in eine LinkedHashMap, die in sortierter Reihenfolge iteriert.

Was man aus der Ausführung mitnehmen kann:

• Der In-Place-Sort nutzte den verketteten Comparator und lieferte in einem einzigen Aufruf aufsteigendes Alter mit absteigendem Gehalt als Tie-Breaker. Kein zweiter Durchlauf nötig.
• Die Stream-Variante gab eine neue sortierte Liste zurück und ließ die Quell-List.of unberührt. Das ist das richtige Muster, wenn die Eingabe unveränderlich oder geteilt ist.
• Der Aufruf von sort auf einer unveränderlichen Liste warf eine UnsupportedOperationException. Der Sort ist in place, und "in place" erfordert Veränderlichkeit.
• Das Map-Ranking landete in einer LinkedHashMap, sodass die Iteration der Sortierreihenfolge entspricht. Hätten wir das dreiargumentige toMap verwendet, wäre das Ergebnis eine HashMap und die Reihenfolge verloren gegangen.

Was kommt als Nächstes

Sie können jetzt jede Liste ordnen und eine sortierte Kopie erstellen, ohne die Quelle zu verändern. Suchen ist die nächste Operation — das Finden eines Elements per Prädikat, per Gleichheit oder per binärer Suche auf einer bereits sortierten Liste. Das nächste Kapitel ist Java Collections durchsuchen.

Übungen