Sortieralgorithmen: Ultimate Guide - Feature-Bild

Sortieralgorithmen [Ultimate Guide]

​​​​von Sven Woltmann – 11. Juni 2020

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.

Momentan sind noch nicht alle Teile dieser Serie fertig. Wo die Beschreibung eines Sortieralgorithmus noch fehlt, habe ich stattdessen auf Wikipedia-Artikel verlinkt – diese gehen allerdings teilweise ziemlich formal an die Sache heran.

Die Quellcodes der gesamten Artikelserie findest du in meinem GitLab-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):

Sortieralgorithmen: linearer vs. quadratischer Aufwand

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

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.

Sortieralgorithmen: Zeitkomplexität

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:

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 im Abschnitt Counting 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.

AlgorithmusZeit
best case
Zeit
avg. case
Zeit
worst case
PlatzStabil
Insertion SortO(n)O(n²)O(n²)O(1)Ja
Selection SortO(n²)O(n²)O(n²)O(1)Nein
Bubble SortO(n)O(n²)O(n²)O(1) Ja
Quicksort
(Wikipedia)
O(n log n)O(n log n)O(n²)O(log n)Nein
Mergesort
(Wikipedia)
O(n log n)O(n log n)O(n log n)O(n)Ja
Heapsort
(Wikipedia)
O(n log n)O(n log n)O(n log n)O(1)Nein
Counting Sort
(Wikipedia)
O(n + k)O(n + k)O(n + k)O(k)Ja

(Die Variable k bei Counting Sort steht für keys – die Anzahl der möglichen Werte.)

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
PlatzStabil
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
PlatzStabil
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
PlatzStabil
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
PlatzStabil
O(n log n)O(n log n)O(n²)O(1)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
PlatzStabil
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
PlatzStabil
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 kleinergröß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
PlatzStabil
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).

Sonstige Sortieralgorithmen

Es gibt zahlreiche weitere Sortieralgorithmen (Shell Sort, Comb Sort, Bucket Sort, Radix 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 trage dich gerne über das folgende Formular in meinen E-Mail-Verteiler ein.

  •  
  •  
  •  
  •  
  •  
  •  

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Pflichtfelder sind markiert.

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}