Sortieralgorithmen [Ultimate Guide]
Artikelserie: Sortieralgorithmen
Teil 1: Einführung
(Melde dich für den HappyCoders-Newsletter an,
um sofort über neue Teile informiert zu werden.)
Sortieralgorithmen sind Thema jeder Informatiker-Ausbildung. Viele von uns haben irgendwann einmal die genaue Funktionsweise von Insertion Sort bis Merge- und Quicksort auswendig lernen müssen, einschließlich deren Zeitkomplexitäten im best, average und worst case in Big-O-Notation ... um nach der Prüfung das meiste davon wieder zu vergessen ;-)
Wenn du eine Auffrischung brauchst, wie die gebräuchlichsten Sortieralgorithmen funktionieren und wie sie sich unterscheiden, ist diese Artikelserie genau das Richtige für dich.
Dieser erste Artikel behandelt folgende Fragen:
- Welches sind die gebräuchlichsten Sortierverfahren?
- In welchen Eigenschaften unterscheiden sie sich?
- Wie ist das Laufzeitverhalten der einzelnen Sortiermethoden (Platz- und Zeitkomplexität)?
Möchtest du wissen, wie ein bestimmter Sortieralgorithmus genau funktioniert? Jedes aufgelistete Sortierverfahren linkt zu einem vertiefenden Artikel, welcher...
- die Funktionsweise des jeweiligen Verfahrens anhand eines Beispiels erklärt,
- die Zeitkomplexität herleitet (auf anschauliche Weise, ohne komplizierte mathematische Beweise),
- zeigt, wie man den jeweiligen Sortieralgorithmus in Java implementiert, und
- die Performance der Java-Implementierung misst und mit dem theoretischen Laufzeitverhalten abgleicht.
Die Quellcodes der gesamten Artikelserie findest du in meinem GitHub-Repository.
Eigenschaften von Sortieralgorithmen
Sortierverfahren unterscheiden sich hauptsächlich in den folgenden Eigenschaften (Erklärungen findest du in den folgenden Abschnitten):
- Geschwindigkeit (oder besser: Zeitkomplexität)
- Platzkomplexität
- Stabilität
- Vergleichsbasiert / nicht-vergleichsbasiert
- Parallelisierbarkeit
- Rekursiv / nicht rekursiv
- Adaptionsfähigkeit
Du kannst die Erklärungen auch erstmal überspringen und später hierher zurückkehren. Hier geht es direkt zu den wichtigsten Sortieralgorithmen.
Zeitkomplexität von Sortieralgorithmen
Das wichtigste Kriterium bei der Auswahl eines Sortierverfahrens ist in den meisten Fällen dessen Geschwindigkeit. Interessant ist hierbei in erster Linie, wie sich die Geschwindigkeit in Abhängigkeit von der Anzahl der zu sortierenden Elemente ändert.
Denn ein Algorithmus kann bei hundert Elementen doppelt so schnell sein wie ein anderer, bei tausend Elementen aber durchaus fünf mal langsamer (oder noch viel viel langsamer; aber das ließ sich nicht mehr gut in dem Diagramm abbilden):
Deshalb gibt man die Laufzeit eines Algorithmus im allgemeinen als Zeitkomplexität in der sogenannten "O-Notation" (englisch: "Big O notation") an.
Die folgenden Klassen von Zeitkomplexitäten sind für Sortieralgorithmen relevant (detailliertere Beschreibungen dieser Komplexitätsklassen findest Du in dem jeweils verlinkten Artikel):
- O(n) (ausgesprochen "O von n"): linearer Aufwand – für doppelt so viel Elemente benötigt die Sortiermethode doppelt so lange;
- O(n log n) (ausgesprochen "O von n log n"): quasi-linearer Aufwand – fast so gut wie linearer Aufwand;
- O(n²) (ausgesprochen: "O von n Quadrat"): quadratischer Aufwand – für doppelt so viele Elemente benötigt die Sortierfunktion viermal so lange, für 10× so viele Elemente 100× so lang, für 1000× so viele Elemente 1.000.000× so lang, usw.
Hier noch einmal das Diagramm von oben mit der Angabe der Zeitkomplexitäten und einer zusätzlichen Kurve für quasilinearen Aufwand. Da die Zeitkomplexität keine Aussage über die absolut benötigten Zeiten macht, sind die Achsen hier nicht mehr mit Werten beschriftet.
Bei quadratischer Komplexität stößt man relativ schnell an die Leistungsgrenzen heutiger Hardware:
Während Quicksort auf meinem Laptop eine Milliarde Elemente in 90 Sekunden sortiert, breche ich den Versuch mit Insertion Sort nach einer Viertelstunde ab. Ausgehend von etwa 100 Sekunden für eine Million Elemente, würde Insertion Sort für eine Milliarde Elemente beeindruckende drei Jahre und zwei Monate brauchen.
Quadratische Komplexität sollte also, wenn möglich, vermieden werden.
Platzkomplexität von Sortieralgorithmen
Nicht nur Zeitkomplexität ist für Sortierverfahren relevant, sondern auch die Platzkomplexität. Diese gibt an, wie viel zusätzlichen Speicherplatz der Algorithmus in Abhängigkeit von der Anzahl der zu sortierenden Elemente benötigt. Damit ist nicht der Speicherplatz gemeint, der für die zu sortierenden Elemente selbst benötigt wird, sondern darüberhinaus benötigter Platz für z. B. Hilfsvariablen, Schleifenzähler und temporäre Arrays.
Platzkomplexität wird mit den gleichen Klassen angegeben wie Zeitkomplexität. Hier treffen wir noch auf eine weitere Klasse:
- O(1) (ausgesprochen "O von 1"): konstanter Aufwand – bei vielen Sortieralgorithmen ist der zusätzliche Speicherbedarf unabhängig von der Anzahl der zu sortierenden Elemente.
Stabile und nicht-stabile Sortierverfahren
Bei stabilen Sortierverfahren wird die relative Reihenfolge von Elementen, die den gleichen Sortierschlüssel haben, beibehalten. Bei nicht-stabilen Sortierverfahren wird dies nicht garantiert: Die relative Reihenfolge kann beibehalten werden, muss es aber nicht.
Was bedeutet das?
In folgendem Beispiel haben wir eine Namensliste (zufällig erstellt mit dem "Real Name Creator" – mit kleiner manueller Anpassung, um zweimal den gleichen Nachnamen zu erhalten). Die Liste ist zunächst nach Vornamen sortiert:
| Annika Weigert |
| Fabio Müller |
| Gertrud Selig |
| Jonathan Heydrich |
| Mathias Müller |
| Waltraud Birke |
Diese Liste soll nun – ohne die Vornamen zu betrachten – nach Nachnamen sortiert werden. Wenn wir dafür ein stabiles Sortierverfahren anwenden, ist das Ergebnis immer:
| Waltraud Birke |
| Jonathan Heydrich |
| Fabio Müller |
| Mathias Müller |
| Annika Weigert |
| Gertrud Selig |
D. h. die Reihenfolge von Fabio und Mathias bleibt bei einem stabilen Sortierverfahren immer unverändert. Bei einem unstabilen Sortierverfahren kann auch folgendes Sortierergebnis herauskommen:
| Waltraud Birke |
| Jonathan Heydrich |
| Mathias Müller |
| Fabio Müller |
| Annika Weigert |
| Gertrud Selig |
Mathias und Fabio sind hierbei gegenüber der Ausgangsreihenfolge vertauscht.
Vergleichsbasierte und nicht-vergleichsbasierte Sortierverfahren
Die meisten der bekannten Sortierverfahren basieren auf dem Vergleich zweier Elemente auf kleiner, größer oder gleich. Es existieren jedoch auch nicht-vergleichsbasierte Sortieralgorithmen.
Wie das funktionieren kann, erfährst du in den Abschnitten Counting Sort und Radix Sort.
Parallelisierbarkeit
Diese Eigenschaft beschreibt, ob und in wie weit sich ein Sortieralgorithmus für die parallele Abarbeitung auf mehreren CPU Cores eignet.
Rekursive / nicht-rekusive Sortiermethoden
Ein rekursiver Sortieralgorithmus benötigt zusätzlichen Speicherplatz auf dem Stack. Bei zu tiefer Rekursion droht die gefürchtete StackOverflowExecption.
Adaptionsfähigkeit (adaptability)
Ein adaptiver Sortieralgorithmus kann sein Verhalten während der Laufzeit an bestimmte Eingabedaten (z. B. vorsortierte Elemente) anpassen und diese deutlich schneller sortieren als zufällig verteilte Elemente.
Vergleich der wichtigsten Sortieralgorithmen
Die folgende Tabelle gibt einen Überblick über alle in dieser Artikelserie vorgestellten Sortieralgorithmen. Es handelt sich um eine Auswahl der am meisten verbreitetsten Sortierverfahren. Dies sind auch die, die man in der Regel in der Informatik-Ausbildung lernt.
Jeder Eintrag ist verlinkt zu einem vertiefenden Artikel, der den jeweiligen Algorithmus und dessen Eigenschaften im Detail beschreibt und auch dessen Quellcode enthält.
Wenn dir zunächst ein Überblick genügt, findest du im Anschluss an die Tabelle die Sortieralgorithmen in jeweils einem Satz erklärt.
| Algorithmus | Zeit best case | Zeit avg. case | Zeit worst case | Platz | Stabil |
|---|---|---|---|---|---|
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Ja |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Nein |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Ja |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Nein |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Nein |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Ja |
| Radix Sort | O(k · (b + n)) | O(k · (b + n)) | O(k · (b + n)) | O(b + n) | Ja |
Die Variable k steht bei Counting Sort steht für keys (die Anzahl der möglichen Schlüsselwerte) und bei Radix Sort für key length (die maximale Länge eines Schlüssels). Die Variable b bei Radix Sort steht für Basis.
Einfache Sortierverfahren
Einfache Sortierverfahren sind gut geeignet, um kleine Listen zu sortieren. Für große Listen sind sie aufgrund des quadratischen Aufwands ungeeignet. Insbesondere Insertion Sort (was aufgrund von weniger Vergleichen ungefähr doppelt so schnell ist wie Selection Sort) wird gerne verwendet, um effiziente Sortieralgorithmen wie Quicksort und Mergesort weiter zu optimieren. Dazu lässt man diese Verfahren kleine Teillisten im Größenbereich bis ca. 50 Elemente mit Insertion Sort sortieren.
Insertion Sort
Insertion Sort verwendet man zum Beispiel beim Sortieren von Spielkarten: man nimmt eine Karte nach der anderen auf und fügt sie an der richtigen Stelle in die bereits sortieren Karten ein (auf deutsch: Einfüge-Sortieren).
| Zeit best case | Zeit avg. case | Zeit worst case | Platz | Stabil |
|---|---|---|---|---|
| O(n) | O(n²) | O(n²) | O(1) | Ja |
Selection Sort
Selection Sort kannst du dir anhand des Spielkartenbeispiels so vorstellen, dass alle einzusortierenden Karten offen vor dir liegen. Du suchst die kleinste Karte und nimmst sie auf, dann suchst du die nächstgrößere Karte und nimmst sie rechts neben die zuerst aufgenommene Karte, usw. bis du als letztes die größte Karte aufnimmst und nach ganz rechts auf die Hand nimmst.
| Zeit best case | Zeit avg. case | Zeit worst case | Platz | Stabil |
|---|---|---|---|---|
| O(n²) | O(n²) | O(n²) | O(1) | Nein |
Bubble Sort
Bei Bubble Sort werden von links nach rechts jeweils nebeneinanderliegende Elemente verglichen und – falls diese in der falschen Reihenfolge vorliegen – miteinander vertauscht. Dieser Vorgang wird so oft wiederholt bis alle Elemente sortiert sind.
| Zeit best case | Zeit avg. case | Zeit worst case | Platz | Stabil |
|---|---|---|---|---|
| O(n) | O(n²) | O(n²) | O(1) | Ja |
Effiziente Sortierverfahren
Effiziente Sortieralgorithmen erreichen eine deutlich bessere Zeitkomplexität von O(n log n). Sie eignen sich daher auch für große Datensätze mit Milliarden von Elementen.
Quicksort
Quicksort funktioniert nach dem "Teile und Herrsche"-Prinzip. Durch eine sogenannte Partitionierung wird der Datensatz zunächst grob in kleine und große Elemente aufgeteilt: kleine kommen nach links, große nach rechts. Jede dieser Partitionen wird danach rekursiv wieder partitioniert, solange bis eine Partition nur noch ein Element enthält und damit als sortiert gilt.
Sobald für alle Partionen und Teil-Partitionen die tiefste Rekursionsstufe erreicht ist, ist die gesamte Liste sortiert.
Quicksort hat zwei Nachteile:
- Im worst case (bei absteigend sortierten Elementen) ist die Zeitkomplexität O(n²).
- Quicksort ist nicht stabil.
| Zeit best case | Zeit avg. case | Zeit worst case | Platz | Stabil |
|---|---|---|---|---|
| O(n log n) | O(n log n) | O(n²) | O(log n) | Nein |
Mergesort
Mergesort funktioniert ebenfalls nach dem "Teile und Herrsche"-Prinzip. Wobei hier sozusagen in umgekehrter Reihenfolge vorgegangen wird wie bei Quicksort: Anstatt zuerst zu sortieren und dann in die Rekursion abzusteigen, geht Mergesort zuerst in die Rekursion, bis Teillisten mit nur noch einem Element erreicht sind und fügt dann jeweils zwei Teillisten so zusammen ("merged" sie), dass eine sortierte Teilliste entsteht.
Beim letzten Schritt aus der Rekursion heraus werden zwei verbleibende Teillisten gemerged und ergeben das sortierte Gesamtergebnis.
Mergesort hat gegenüber Quicksort den Vorteil, dass auch im worst case die Zeitkomplexität O(n log n) nicht überschreitet und dass es stabil ist. Allerdings erkauft man sich diese Vorteile durch einen zusätzlichen Platzbedarf in der Größenordnung O(n).
| Zeit best case | Zeit avg. case | Zeit worst case | Platz | Stabil |
|---|---|---|---|---|
| O(n log n) | O(n log n) | O(n log n) | O(n) | Ja |
Heapsort
Der Begriff Heapsort ist für Java-Entwickler oft verwirrend, da man ihn zunächst mit dem Java Heap in Verbindung bringt. Die Heaps von Heapsort und Java sind allerdings zwei völlig unterschiedliche Dinge.
Heapsort arbeitet mit der Datenstruktur Heap, einem auf ein Array abgebildeter Binärbaum, in dem jeder Knoten größer oder gleich seiner Kinder ist. Das größte Element liegt also immer auf der Wurzelposition.
Dieses Wurzelelement wird entnommen, dann wird das letzte Element auf die Wurzelposition gesetzt und danach der Baum per "Heapify"-Operation repariert, woraufhin wiederum das größte der verbleibenden Element auf der Wurzelposition liegt. Der Prozess wird solange wiederholt, bis der Baum leer ist. Die dem Baum entnommenen Elemente ergeben das sortierte Ergebnis.
| Zeit best case | Zeit avg. case | Zeit worst case | Platz | Stabil |
|---|---|---|---|---|
| O(n log n) | O(n log n) | O(n log n) | O(1) | Nein |
Nicht vergleichsbasierte Sortierverfahren
Nicht vergleichsbasierte Sortierverfahren basieren nicht auf dem Vergleich zweier Element auf kleiner, größer oder gleich.
Wie können sie dann funktionieren?
Am besten lässt sich das an einem Beispiel erklären – im folgenden anhand von Counting Sort.
Counting Sort
Bei Counting Sort werden Elemente – wie der Name schon sagt – gezählt. Um beispielsweise ein Array mit Zahlen aus dem Bereich 1 bis 10 zu sortieren, zählen wir (in einem einzigen Durchgang), wie oft die 1 vorkommt, wie oft die 2, usw. bis zur 10.
Im zweiten Durchgang schreiben wir dann die 1 so oft von links beginnend in das Array, wie sie vorkommt, dann die 2 so oft, wie diese vorkommt, usw. wiederum bis zur 10.
Dieses Verfahren wird in der Regel nur für kleine Zahlentypen wie byte, char oder short eingesetzt, oder wenn der Bereich der zu sortierenden Zahlen bekannt ist (z. B. ints zwischen 0 und 150). Der Grund dafür ist, dass wir für das Zählen der Elemente ein zusätzliches Array entsprechend der Größe des Zahlenbereichs benötigen.
| Zeit best case | Zeit avg. case | Zeit worst case | Platz | Stabil |
|---|---|---|---|---|
| O(n + k) | O(n + k) | O(n + k) | O(k) | Ja |
Die Variable k steht für die Anzahl der möglichen Werte (keys).
Radix Sort
Bei Radix Sort werden die Elemente Ziffer für Ziffer sortiert. Dreistellige Zahlen z. B. zuerst nach den Einerstellen, dann nach den Zehnerstellen und zuletzt nach den Hunderterstellen.
Dieses Verfahren eignet sich im Gegensatz zu Counting Sort auch für große Zahlenräume wie int und long, ist stabil und kann sogar schneller sein als Quicksort, hat jedoch mit O(n) eine höhere Platzkomplexität und wird daher seltener eingesetzt.
| Zeit best case | Zeit avg. case | Zeit worst case | Platz | Stabil |
|---|---|---|---|---|
| O(k · (b + n)) | O(k · (b + n)) | O(k · (b + n)) | O(n) | Ja |
Sonstige Sortieralgorithmen
Es gibt zahlreiche weitere Sortieralgorithmen (Shell Sort, Comb Sort, Bucket Sort, um nur ein paar zu nennen). Die in diesem Artikel vorgestellten Methoden zu kennen stellt meiner Meinung nach jedoch ein sehr gutes Grundlagenwissen dar.
Falls du dir die Javadocs von List.sort() und Arrays.sort() durchgelesen hast, fragst du dich vielleicht, warum ich hier Timsort und Dual-Pivot Quicksort nicht aufführe.
Timsort ist kein komlett eigenständiges Sortierverfahren. Vielmehr ist es eine Kombination aus Mergesort, Insertion Sort und etwas zusätzlicher Logik. Ich werde Timsort im Artikel über Mergesort beschreiben.
Ebenso ist Dual-Pivot Quicksort eine Variante des regulären Quicksort und wird im entsprechenden Artikel beschrieben werden.
Zusamenfassung
Dieser Artikel hat einen Überblick über die gängigsten Sortieralgorithmen gegeben und die Eigenschaften beschrieben, in denen sich diese hauptsächlich unterscheiden.
In den folgenden Teilen dieser Serie beschreibe ich je einen Sortieralgorithmus im Detail – anhand von Beispielen und mit Quellcodes.
In einem weiteren Teil gebe ich einen Überblick über die Sortiermethoden, die Java bereitstellt, und zeige, wie man zum einen primitive Datentypen sortiert und zum anderen Objekte mit Hilfe von Comparator und Comparable.
Wenn dir der Artikel gefallen hat, teile ihn gerne über einen der Share-Buttons am Ende. Möchtest du per E-Mail informiert werden, wenn ich einen neuen Artikel veröffentliche? Dann klicke hier, um dich in den HappyCoders-E-Mail-Verteiler einzutragen.