Sortieralgorithmen — Bubble Sort, Merge Sort und Quick Sort im Vergleich

Ein Sortieralgorithmus ordnet dieselben Elemente neu an, zum Beispiel vom kleinsten zum größten. Wenn du zuerst die kurze Antwort willst: Bubble Sort ist einfach, aber für große Listen meist zu langsam, Merge Sort liefert zuverlässig eine Laufzeit von $O(n \log n)$, und Quick Sort ist in der Praxis oft schnell, wenn die Partitionen einigermaßen ausgeglichen bleiben.

Die richtige Frage ist nicht „welcher Sortieralgorithmus ist der beste?“, sondern „der beste unter welchen Bedingungen?“. Bubble Sort veranschaulicht lokale Vertauschungen, Merge Sort zeigt Divide-and-Conquer besonders klar, und Quick Sort zeigt, warum die durchschnittliche Geschwindigkeit stark sein kann, auch ohne Garantie für den schlechtesten Fall.

Was Sortieralgorithmen tun

Gegeben sei eine Liste wie $[5, 1, 4, 2]$. Der Algorithmus soll dieselben Werte sortiert zurückgeben:

$$[1, 2, 4, 5]$$

Das klingt einfach, aber verschiedene Algorithmen erreichen dieses Ergebnis auf sehr unterschiedliche Weise. Die wichtigsten Unterschiede sind:

• wie sie Elemente verschieben
• wie viele Vergleiche oder Vertauschungen sie typischerweise brauchen
• wie viel zusätzlichen Speicher sie benötigen
• wie empfindlich sie auf ungünstige Eingabemuster reagieren

Bubble Sort: Wiederholte Vertauschungen benachbarter Elemente

Bubble Sort geht die Liste durch und vertauscht benachbarte Elemente, die in der falschen Reihenfolge stehen. Nach einem vollständigen Durchlauf ist das größte noch unsortierte Element nach hinten „aufgestiegen“.

Bei $[5, 1, 4, 2]$ sieht der erste Durchlauf so aus:

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

Dann wiederholt sich das für den verbleibenden unsortierten Teil, bis keine Vertauschungen mehr nötig sind.

Bubble Sort ist vor allem zum Lernen nützlich. Im Allgemeinen hat er eine Zeitkomplexität von $O(n^2)$, daher wächst die Zahl der Vergleiche schnell, wenn die Liste größer wird. Für kleine Beispiele im Unterricht ist das in Ordnung. Für ernsthafte Sortieraufgaben ist er meist nicht die richtige Wahl.

Merge Sort: Teilen, sortieren, dann zusammenführen

Merge Sort verwendet die Idee von Divide-and-Conquer. Er teilt die Liste in kleinere Teile, sortiert diese Teile und führt die sortierten Stücke dann wieder zusammen.

Für $[5, 1, 4, 2]$ ist eine übersichtliche Darstellung:

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

Sortiere jede Hälfte:

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

Führe dann die beiden sortierten Hälften zusammen:

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

Die größte Stärke von Merge Sort ist seine Vorhersagbarkeit. Seine Laufzeit ist in der üblichen Analyse $O(n \log n)$, nicht nur im Durchschnitt. Der Hauptnachteil ist der Speicherbedarf: Gängige arraybasierte Implementierungen verwenden beim Zusammenführen zusätzlichen Speicher.

Quick Sort: Partitionieren um ein Pivot-Element

Quick Sort nutzt ebenfalls Divide-and-Conquer, aber auf andere Weise. Er wählt ein Pivot-Element, legt kleinere Elemente auf die eine Seite und größere auf die andere und sortiert dann beide Seiten rekursiv.

Mit dem Pivot $4$ bei $[5, 1, 4, 2]$ ist eine mögliche Partition:

$$[1, 2] \;|\; 4 \;|\; [5]$$

Jetzt sind der linke und rechte Teil viel kleiner, sodass das Sortieren schnell abgeschlossen ist.

Quick Sort ist in der Praxis oft schnell, weil viele Implementierungen in place partitionieren und das Problem schnell verkleinern, wenn das Pivot die Liste einigermaßen gut aufteilt. Aber diese Bedingung ist wichtig. Wenn die Pivot-Wahl wiederholt schlecht ist, zum Beispiel immer wieder eine winzige Seite und eine fast volle Seite erzeugt, wird der schlechteste Fall zu $O(n^2)$.

Bubble Sort vs. Merge Sort vs. Quick Sort

Algorithmus	Grundidee	Typische Laufzeit	Laufzeit im schlechtesten Fall	Zusätzlicher Speicher
Bubble Sort	Wiederholte Vertauschungen benachbarter Elemente	$O(n^2)$	$O(n^2)$	Gering
Merge Sort	Teilen, Hälften sortieren, zusammenführen	$O(n \log n)$	$O(n \log n)$	Höher bei gängigen Array-Implementierungen
Quick Sort	Partitionieren um ein Pivot-Element	Oft $O(n \log n)$	$O(n^2)$	Oft geringer als bei Merge Sort

Wenn du eine praktische Kernaussage mitnehmen willst, dann diese: Bubble Sort ist ein Lehralgorithmus, Merge Sort ist die stabile und vorhersagbare Option, und Quick Sort ist oft die praktische Wahl für hohe Geschwindigkeit, wenn die Implementierung gut mit Pivot-Elementen umgeht.

Ein durchgerechnetes Beispiel mit derselben Liste

Verwende dieselbe Liste:

$$[5, 1, 4, 2]$$

Bubble Sort korrigiert immer wieder lokale Fehler. Er „sieht“ nicht die gesamte Struktur und kann deshalb viele Durchläufe brauchen.

Merge Sort zerlegt das Problem zuerst in kleinere sortierte Teile und kombiniert sie dann. Diese Struktur ist der Grund, warum seine Leistung auch bei größeren Listen zuverlässig bleibt.

Quick Sort versucht früh eine starke Aufteilung zu erreichen. Wenn die Aufteilung ausreichend ausgeglichen ist, schrumpft die restliche Arbeit schnell.

Deshalb merken sich Studierende die Komplexitätsangaben oft besser, nachdem sie gesehen haben, wie sich dieselbe Liste durch jede Methode verändert. Die Zahlen sind keine willkürlichen Etiketten. Sie spiegeln wider, wie der Algorithmus Unordnung reduziert.

Häufige Fehler beim Vergleichen von Sortieralgorithmen

Annehmen, dass Quick Sort immer schneller ist

Quick Sort ist in der Praxis oft schnell, aber nicht in jedem Fall garantiert der schnellste. Schlechte Pivot-Wahl kann ihn stark ausbremsen.

$O(n \log n)$-Algorithmen als identisch behandeln

Merge Sort und Quick Sort können dieselbe durchschnittliche Wachstumsrate haben, ohne sich bei Speicherverbrauch, Garantien für den schlechtesten Fall oder Implementierungsdetails gleich zu verhalten.

Bubble Sort verwenden, weil er leicht zu programmieren ist

Leicht zu programmieren zu sein ist nicht dasselbe wie geeignet zu sein. Für kleine Demonstrationen ist Bubble Sort in Ordnung. Für größere reale Eingaben macht er meist unnötige Arbeit.

Das Eingabemodell vergessen

Diese Vergleiche gehen meist von vergleichsbasiertem Sortieren bei allgemeinen Eingaben aus. Wenn die Daten eine besondere Struktur haben, können nicht vergleichsbasierte Verfahren wie Counting Sort die Entscheidung vollständig verändern.

Wann welcher Sortieralgorithmus verwendet wird

Bubble Sort wird hauptsächlich zum Lehren, Nachvollziehen und für sehr kleine Beispiele verwendet, bei denen Verständlichkeit wichtiger ist als Leistung.

Merge Sort wird verwendet, wenn ein konsistentes Verhalten von $O(n \log n)$ wichtig ist und zusätzlicher Speicher akzeptabel ist. Je nach Implementierung eignet er sich auch gut für verkettete Listen und für Situationen, in denen stabiles Sortieren wichtig ist.

Quick Sort wird verwendet, wenn praktische Geschwindigkeit wichtig ist und die Implementierung eine gute Pivot-Strategie oder Schutzmechanismen als Fallback hat. Viele Sortierstrategien in Standardbibliotheken verwenden Quick-Sort-Ideen zusammen mit Absicherungen statt einer naiven Lehrbuchversion.

Eine schnelle Art, sich den Unterschied zu merken

Merke sie dir über die Bewegung:

• Bubble Sort korrigiert Nachbarn
• Merge Sort baut sortierte Hälften auf
• Quick Sort teilt um ein Pivot-Element

Dieses mentale Bild ist nützlicher, als sich drei Namen und drei Formeln auswendig zu merken.

Probiere deine eigene Version aus

Nimm die Liste $[7, 3, 6, 1]$ und verfolge einen Durchlauf von Bubble Sort, einen Teilungs-und-Zusammenführungs-Zyklus von Merge Sort und eine Pivot-Partition bei Quick Sort. Wenn du erklären kannst, warum sich die Liste in jedem Fall anders verändert, hast du das Konzept verstanden.