Sortieren gehört zu den Aufgaben, die beim Programmieren erstaunlich oft auftauchen. Zahlen sollen der Größe nach angeordnet werden, Namen alphabetisch, Datensätze nach Datum oder Produkte nach Preis. Java kann dir diese Arbeit mit Methoden wie Arrays.sort() zwar bequem abnehmen, aber gerade deshalb lohnt es sich zu verstehen, was beim Sortieren eigentlich passiert.

Sortieralgorithmen sind außerdem ein gutes Beispiel dafür, dass es für dasselbe Problem sehr unterschiedliche Lösungen geben kann. Einige Verfahren sind leicht verständlich, benötigen dafür aber viele Arbeitsschritte. Andere sind deutlich schneller, dafür jedoch komplizierter aufgebaut. Und manchmal hängt die beste Lösung davon ab, wie die Daten aussehen, die du sortieren möchtest.

Wir schauen uns deshalb fünf der bekanntesten Verfahren Schritt für Schritt an. Dabei geht es weniger darum, jeden Algorithmus auswendig programmieren zu können. Viel wichtiger ist, dass du verstehst, welche Idee dahintersteckt, wodurch sich die Verfahren unterscheiden und wie du anschließend prüfen kannst, ob deine Implementierung tatsächlich das tut, was du von ihr erwartest.

Am Ende dieses Artikels kennst du die grundlegende Funktionsweise von Bubble Sort, Selection Sort, Insertion Sort, Merge Sort und Quick Sort, weißt, wodurch sich die Verfahren in der Praxis unterscheiden, und kannst deine eigene Sortierimplementierung gezielt überprüfen.

 

Bubble Sort - immer zwei Nachbarn vergleichen

Beginnen wir mit Bubble Sort. Der Algorithmus ist wahrscheinlich eines der bekanntesten Sortierverfahren überhaupt und gleichzeitig eines der einfachsten zu verstehen.

Angenommen, wir haben folgende Zahlen:

5  2  8  1

Bubble Sort betrachtet immer zwei benachbarte Werte. Sind sie in der falschen Reihenfolge, werden sie vertauscht. Zuerst vergleichen wir also 5 und 2. Da 5 größer ist, tauschen wir beide Werte.

2  5  8  1

Danach werden 5 und 8 verglichen. Hier stimmt die Reihenfolge bereits. Anschließend kommen 8 und 1 an die Reihe und müssen wieder vertauscht werden.

2  5  1  8

Damit ist der erste Durchlauf beendet. Die größte Zahl steht jetzt bereits ganz rechts. Danach beginnt der nächste Durchlauf. Wieder werden benachbarte Elemente verglichen und bei Bedarf vertauscht, bis am Ende keine Änderung mehr notwendig ist.

Eine einfache Java-Implementierung sieht so aus:

for (int i = 0; i < values.length - 1; i++) {
    for (int j = 0; j < values.length - 1 - i; j++) {
        if (values[j] > values[j + 1]) {
            int temp = values[j];
            values[j] = values[j + 1];
            values[j + 1] = temp;
        }
    }
}

Bubble Sort ist leicht nachzuvollziehen, aber bei großen Datenmengen ziemlich langsam. Im ungünstigen Fall liegt seine Laufzeit bei O(n²). Das bedeutet vereinfacht gesagt, dass der Aufwand sehr schnell wächst, wenn die Anzahl der Elemente größer wird.

Für produktiven Code ist Bubble Sort deshalb nur selten eine gute Wahl. Zum Lernen eignet er sich dagegen hervorragend, weil du jeden einzelnen Schritt sehr gut nachvollziehen kannst.

O(n²) beschreibt, wie stark der Aufwand eines Algorithmus wächst, wenn die Anzahl der zu sortierenden Elemente (n) zunimmt. Bei O(n²) verdoppelt sich der Aufwand nicht einfach, wenn du doppelt so viele Elemente hast - er vervierfacht sich, weil der Wert quadriert wird. Bei Bubble Sort, Selection Sort und Insertion Sort kommt das daher, dass für jedes der n Elemente im schlechtesten Fall noch einmal fast alle anderen n Elemente verglichen werden müssen - daraus ergibt sich ungefähr n · n = n² Vergleiche. Konkret bedeutet das: Sortierst du 10 Elemente, sind es rund 100 Vergleichsschritte. Bei 100 Elementen sind es aber nicht 1.000, sondern rund 10.000. Genau dieses überproportionale Wachstum macht O(n²)-Verfahren bei kleinen Datenmengen unproblematisch, bei großen aber zunehmend langsam und erklärt, warum Merge Sort und Quick Sort mit ihrem O(n log n) dort im Vorteil sind.

 

Selection Sort - immer das kleinste Element suchen

Selection Sort verfolgt eine andere Strategie. Statt ständig benachbarte Elemente zu vertauschen, sucht der Algorithmus im noch unsortierten Bereich gezielt nach dem kleinsten Wert.

Wir beginnen wieder mit:

5  2  8  1

Zuerst wird die komplette Liste betrachtet. Der kleinste Wert ist 1. Dieser wird mit dem ersten Element vertauscht.

1  2  8  5

Die 1 steht damit bereits endgültig an der richtigen Position. Der erste Eintrag muss bei den folgenden Durchläufen nicht mehr berücksichtigt werden.

Nun betrachten wir nur noch:

2  8  5

Der kleinste Wert ist 2. Er befindet sich bereits an der richtigen Stelle. Im letzten unsortierten Bereich bleiben schließlich 8 und 5. Hier ist 5 der kleinere Wert, also werden beide vertauscht.

1  2  5  8

Die Grundidee lautet damit immer gleich: Im unsortierten Bereich das kleinste Element suchen, dieses nach vorne setzen und anschließend den sortierten Bereich um eine Position vergrößern.

Der Unterschied zu Bubble Sort ist deutlich. Bubble Sort vergleicht immer benachbarte Werte und verschiebt dadurch große Elemente Schritt für Schritt nach hinten. Selection Sort sucht dagegen gezielt nach dem Element, das als Nächstes an die richtige Position gehört.

Auch Selection Sort arbeitet typischerweise mit O(n²). Besonders viele Vergleiche erspart dir das Verfahren also nicht. Es führt allerdings normalerweise weniger tatsächliche Vertauschungen durch als Bubble Sort.

 

Insertion Sort - Elemente an der richtigen Stelle einfügen

Insertion Sort arbeitet wieder anders. Hier entsteht Schritt für Schritt ein bereits sortierter Bereich.

Du kannst dir das ähnlich wie beim Sortieren von Spielkarten auf der Hand vorstellen. Du nimmst das nächste Element und schiebst es an die richtige Position zwischen die Werte, die du bereits einsortiert hast.

Wir starten erneut mit:

5  2  8  1

Das erste Element betrachten wir zunächst als sortiert. Jetzt kommt die 2 hinzu. Sie ist kleiner als die 5 und muss deshalb davor eingefügt werden.

2  5  8  1

Als Nächstes wird die 8 betrachtet. Sie ist größer als 5 und befindet sich damit bereits an der richtigen Stelle.

Nun kommt die 1. Sie ist kleiner als alle bisherigen Werte und muss entsprechend weit nach vorne geschoben werden.

1  2  5  8

Der wichtige Unterschied zu Selection Sort liegt darin, dass Insertion Sort nicht zuerst den gesamten unsortierten Bereich nach dem kleinsten Wert durchsucht. Stattdessen nimmt der Algorithmus immer das nächste Element und fügt dieses in den bereits sortierten Teil ein.

Im ungünstigen Fall liegt auch Insertion Sort bei O(n²). Trotzdem besitzt das Verfahren eine interessante Eigenschaft: Wenn deine Daten bereits weitgehend richtig sortiert sind, müssen häufig nur wenige Elemente verschoben werden. In solchen Situationen kann Insertion Sort deutlich besser abschneiden, als die Laufzeitklasse zunächst vermuten lässt.

Damit zeigt sich bereits etwas Wichtiges: Nur weil zwei Algorithmen dieselbe theoretische Laufzeit besitzen, müssen sie sich in der Praxis nicht automatisch gleich verhalten.

 

Merge Sort - teilen, sortieren und wieder zusammenführen

Bei größeren Datenmengen werden Verfahren wie Bubble Sort oder Selection Sort schnell unattraktiv. Merge Sort verfolgt deshalb eine grundlegend andere Strategie.

Statt die komplette Liste immer wieder abzulaufen, wird das Problem zunächst in kleinere Teile zerlegt.

Nehmen wir wieder:

5  2  8  1

Merge Sort teilt die Daten zunächst in zwei Bereiche.

5  2    8  1

Diese Bereiche werden erneut geteilt.

5    2    8    1

Ein einzelnes Element ist automatisch sortiert. Jetzt beginnt der eigentliche interessante Teil. Die kleinen Bereiche werden wieder zusammengeführt und dabei direkt richtig sortiert.

Aus 5 und 2 entsteht:

2  5

Aus 8 und 1 entsteht:

1  8

Jetzt müssen nur noch diese beiden bereits sortierten Bereiche zusammengeführt werden. Dabei vergleichst du jeweils die vorderen Elemente miteinander. Zuerst kommt die 1, danach die 2, anschließend die 5 und zum Schluss die 8.

1  2  5  8

Merge Sort verfolgt damit ein anderes Prinzip als die bisherigen Algorithmen. Das große Problem wird zunächst immer weiter verkleinert und anschließend aus den gelösten Teilproblemen wieder zusammengesetzt.

Die typische Laufzeit liegt bei O(n log n) und ist damit bei großen Datenmengen deutlich günstiger als O(n²). Dafür benötigt Merge Sort zusätzlichen Speicher, weil beim Zusammenführen der einzelnen Bereiche normalerweise Hilfsstrukturen verwendet werden.

Du musst O(n log n) dabei nicht mathematisch herleiten können. Entscheidend ist zunächst die praktische Aussage: Wenn die Anzahl der Elemente stark wächst, steigt der Aufwand wesentlich langsamer als bei einem Algorithmus mit O(n²).

 

Quick Sort - sortieren mithilfe eines Pivot-Elements

Quick Sort zerlegt die Daten ebenfalls in kleinere Bereiche, geht dabei aber anders vor als Merge Sort.

Dafür wird zunächst ein sogenanntes Pivot-Element ausgewählt. Nehmen wir vereinfacht die 5.

5  2  8  1

Nun werden die übrigen Werte nacheinander mit dem Pivot verglichen. Zuerst die 2. Sie ist kleiner als 5 und wandert deshalb in den Bereich links vom Pivot.

2  |  5  8  1

Als Nächstes die 8. Sie ist größer als 5 und bleibt deshalb rechts vom Pivot stehen.

2  |  5  8  1

Zum Schluss die 1. Auch sie ist kleiner als 5 und wird ebenfalls nach links einsortiert.

2  1  |  5  |  8

Damit steht die 5 bereits an ihrer endgültigen Position, denn links von ihr befinden sich nur noch kleinere und rechts nur noch größere Werte. Übrig bleiben die beiden Bereiche 2 1 und 8. Nun wird dasselbe Verfahren erneut auf diese Bereiche angewendet. Auch dort wird wieder ein Pivot gewählt und erneut aufgeteilt.

Am Ende entsteht:

1  2  5  8

Quick Sort erreicht im durchschnittlichen Fall ebenfalls eine Laufzeit von O(n log n). Im ungünstigsten Fall kann das Verfahren allerdings auf O(n²) zurückfallen. Wie gut Quick Sort arbeitet, hängt deshalb auch davon ab, wie günstig die Pivot-Elemente gewählt werden und wie gleichmäßig dadurch die Bereiche entstehen.

Spätestens an diesem Punkt wird deutlich, dass es nicht das eine richtige Sortierverfahren für jede Situation gibt. Bubble Sort ist hervorragend geeignet, um das grundsätzliche Prinzip zu verstehen, aber für größere Datenmengen normalerweise keine gute Wahl. Selection Sort arbeitet ebenfalls einfach, führt aber unabhängig von der Ausgangslage viele Vergleiche durch. Insertion Sort kann bei kleinen oder bereits weitgehend sortierten Daten interessant sein. Merge Sort bietet eine zuverlässig gute Laufzeit, benötigt dafür zusätzlichen Speicher. Quick Sort ist in der Praxis häufig sehr schnell, sein Verhalten hängt allerdings stärker von der Aufteilung der Daten ab.

Eine weitere Eigenschaft, auf die du bei Sortieralgorithmen stoßen wirst, ist die Stabilität. Stell dir vor, du hast mehrere Personen gespeichert und sortierst sie ausschließlich nach ihrem Alter. Zwei Personen sind beide 30 Jahre alt. Bei einem stabilen Sortierverfahren bleibt ihre ursprüngliche Reihenfolge untereinander erhalten. Ein instabiles Verfahren garantiert das nicht. Das kann wichtig werden, wenn du Datensätze nach mehreren Kriterien sortierst oder eine vorhandene Reihenfolge erhalten bleiben soll.

In echtem Java-Code wirst du diese Algorithmen trotzdem nur selten selbst implementieren. Für Arrays steht dir beispielsweise bereits Folgendes zur Verfügung:

Arrays.sort(values);

Eine List kannst du unter anderem so sortieren:

values.sort(Comparator.naturalOrder());

Das ist normalerweise die bessere Lösung als eine eigene Implementierung. Die vorhandenen Sortierfunktionen sind getestet und optimiert. Die verschiedenen Algorithmen zu verstehen ist trotzdem wichtig, denn dabei lernst du etwas viel Grundsätzlicheres: Zwei Programme können dasselbe Ergebnis liefern und trotzdem völlig unterschiedlich effizient arbeiten.

Bleibt noch die Frage, wie du überprüfst, ob deine eigene Sortierung korrekt funktioniert. Ein einzelnes Beispiel reicht dafür nicht. Dass am Ende

1  2  5  8

herauskommt, zeigt zunächst nur, dass dieser eine Test funktioniert hat.

Du kannst beispielsweise kontrollieren, ob jedes Element kleiner oder gleich seinem Nachfolger ist:

boolean sorted = true;

for (int i = 0; i < values.length - 1; i++) {
    if (values[i] > values[i + 1]) {
        sorted = false;
        break;
    }
}

Damit weißt du allerdings noch nicht, ob beim Sortieren vielleicht Werte verloren gegangen, verändert oder versehentlich verdoppelt worden sind. Eine sehr praktische Kontrolle besteht deshalb darin, dein Ergebnis mit der Java-Standardbibliothek zu vergleichen.

int[] expected = original.clone();
Arrays.sort(expected);

int[] actual = original.clone();
mySort(actual);

System.out.println(Arrays.equals(expected, actual));

Für einen vernünftigen Test solltest du außerdem nicht immer dieselben Daten verwenden. Ein guter Sortieralgorithmus muss auch mit bereits sortierten Werten, einer umgekehrten Reihenfolge, doppelten Zahlen, negativen Zahlen, einem einzelnen Element und einem leeren Array zurechtkommen.

Damit überprüfst du allerdings nur das Ergebnis. Ob du tatsächlich den geforderten Algorithmus implementiert hast, ist eine andere Frage. Bubble Sort, Selection Sort, Insertion Sort, Merge Sort und Quick Sort können schließlich alle dasselbe korrekt sortierte Array erzeugen.

Wenn eine Aufgabe ausdrücklich Bubble Sort verlangt, musst du deshalb auch darauf achten, ob wirklich benachbarte Elemente verglichen und vertauscht werden. Bei Selection Sort solltest du erkennen können, dass immer nach dem kleinsten Element des unsortierten Bereichs gesucht wird. Bei Insertion Sort muss ein wachsender sortierter Bereich entstehen. Merge Sort sollte die Daten aufteilen und anschließend sortiert zusammenführen, während Quick Sort seine Bereiche anhand von Pivot-Elementen bildet.

Genau darin liegt der eigentliche Wert dieser Algorithmen. Das Ergebnis ist am Ende fast langweilig: Die Werte sind sortiert. Interessant ist der Weg dorthin.

Und genau das begegnet dir beim Programmieren ständig. Eine Lösung kann fachlich korrekt sein und trotzdem unnötig langsam, kompliziert oder für die vorhandenen Daten ungeeignet. Wenn du die grundlegenden Unterschiede zwischen diesen fünf Sortierverfahren verstanden hast, hast du deshalb weit mehr gelernt als nur verschiedene Möglichkeiten, Zahlen in die richtige Reihenfolge zu bringen.