Bubblesort, Mergesort und Quicksort sind die drei klassischen Sortieralgorithmen, die in vielen Algorithmik-Klausuren gefragt werden. Sie unterscheiden sich in Komplexität, Speicherbedarf und Stabilität, daher musst du wissen welcher wann gewählt wird. Du lernst hier den direkten Vergleich der drei Verfahren in einer Tabelle (Best/Average/Worst Case, Speicher, Stabilität, In-Place), warum Quicksort nur mit guter Pivotstrategie in der Praxis empfohlen wird (sonst Worst Case O(n2)), warum Mergesort bei garantierter Worst-Case-Laufzeit oder Stabilitäts-Anforderung gewählt wird, warum randomisierte Pivot-Wahl den Quicksort-Worst-Case verschwindend unwahrscheinlich macht (Erwartungswert bleibt O(nlogn)), und warum Speicher bei QuicksortO(logn) Average aber O(n) Worst Case ist (degenerierte Rekursion).
Die Kernunterschiede in einer Tabelle:
Bubblesort: O(n²) Avg+Worst, O(1) Speicher, stabil, in-place. Lehrbeispiel, in der Praxis zu langsam
Quicksort: O(n log n) Avg, O(n²) Worst, O(log n) Speicher, nicht stabil, in-place. Schnellster in der Praxis, kann degenerieren
In Klausuren wirst du oft gefragt: welcher Algorithmus bei dieser Eingabe / diesem Constraint?. Faustregel: Quicksort als Default, Mergesort wenn Stabilität oder garantierte O(n log n) gefordert, Bubblesort nie außer als Lehrbeispiel.
Wichtig zum Stack-Speicher bei Quicksort: der Rekursionsstack ist O(logn) im Average Case und O(n) im Worst Case (wenn der Pivot wiederholt schlecht gewählt wird und die Partition entartet). Mit Tail-Call-Optimierung und "rekursiv zuerst auf die kleinere Partition" lässt sich der Stack auf O(logn) Worst-Case begrenzen. Das ist nicht der Daten-Speicher (Array bleibt in-place), sondern der Stack-Speicher der Rekursion.
Anforderung
Wähle
Stabilität gefordert
Mergesort (oder Insertion Sort bei kleinem n)
Garantiert O(nlogn) Worst Case
Mergesort oder Heapsort
In-Place, Speicher kritisch
Quicksort mit Random-Pivot oder Heapsort
Sehr kleines n (z. B. n<30)
Insertion Sort (kleine Konstanten)
Daten teilweise sortiert
Timsort/Insertion Sort (adaptiv)
Klausur-Lehrbeispiel
Bubblesort (nie produktiv)
Wenn-dann-Kurzform für die Klausur:
Wenn ...
dann ...
Stabilität nötig
Mergesort
Speicher knapp, Stabilität egal
Quicksort mit Random-Pivot
Garantierte O(nlogn) Worst Case
Mergesort oder Heapsort
Sehr kleines n (Mikro-Benchmark)
Insertion Sort
Daten fast sortiert
Timsort oder Insertion Sort
Lehr-Trace in Klausur
Bubblesort
Wir tracen einen ersten Lomuto-Partition-Schritt mit Pivot 5 (letztes Element):
j
arr[j]
≤5?
i nach
Array
0
3
ja
0
[3,1,4,1,5]
1
1
ja
1
[3,1,4,1,5]
2
4
ja
2
[3,1,4,1,5]
3
1
ja
3
[3,1,4,1,5]
Finaler Pivot-Tausch: arr[i+1]=arr[4], hier 5 mit 5 → keine Änderung. Pivot-Index = 4. Komplette Partition liefert [3,1,4,1,5], alle Werte links sind ≤5. Rekursive Calls dann auf [3,1,4,1] und auf den leeren rechten Bereich. Beobachtung: schlecht gewählter Pivot (Maximum) führt zu 0+(n-1)-Split, klassischer Worst-Case-Auslöser bei sortiertem Input.
Bubblesort, wann wählen? Nur didaktisch. Für jedes praktische n>50 ist er unbrauchbar (Quadratur kostet zu viel). Warum nicht? Average und Worst Case beide O(n2), ~n2/2 Vergleiche. Klausurfalle: "Bubblesort ist immer O(n2)", falsch, mit Early-Exit ist Best Case O(n).
Mergesort, wann wählen? Wenn Stabilität gefordert oder garantierteO(nlogn) Worst-Case-Laufzeit nötig (z. B. Echtzeit-Anwendungen). Warum nicht? Wenn Speicher kritisch ist, weil typisch O(n) Hilfsarray nötig. Klausurfalle: Stabilität-Beweis "warum ist Mergesort stabil?", wegen ≤ im Merge-Schritt, gleiche Werte aus L vor gleichen aus R.
Quicksort, wann wählen? Wenn Speicher knapp und Stabilität egal. In der Praxis oft sehr schnell wegen guter Cache-Lokalität, kann aber ohne Absicherung degenerieren. Warum nicht? Bei sortiertem Input mit naiver Pivot-Wahl → O(n2). Klausurfalle: "Quicksort ist immer in-place", Array ja, Rekursionsstack aber bis O(n) tief.
Praxis außerhalb der Algorithmik-Quellen (optional, nicht durch CLRS/Sedgewick/Ottmann gedeckt):
Niemand schreibt selbst Sortierfunktionen für die Praxis. Standard-Bibliotheken haben hochoptimierte Hybride:
JavaArrays.sort(): Timsort für Objekte (Mergesort + Insertion Sort), Dual-Pivot Quicksort für primitive Typen. Quelle: OpenJDK-Doku.
Pythonsorted(): Timsort. Quelle: CPython-Quelltext und Timsort-Originalbeschreibung von Tim Peters.
Aber im Kopf haben muss man die Klassiker, sie tauchen in jeder Algorithmik-Klausur auf.
Falle 1: "Welcher Algorithmus ist immer am schnellsten?" Antwort: keiner. Quicksort ist im Average Case oft am schnellsten in der Praxis, kann aber auf O(n2) degenerieren. Mergesort garantiert O(nlogn), braucht aber mehr Speicher. Bei kleinem n sind Insertion Sort oder sogar Bubblesort durch geringere Konstanten konkurrenzfähig. Die richtige Antwort hängt immer von Eingabegröße, Eingabestruktur und Speicheranforderung ab.
Falle 2: "Sortieren ist immer O(nlogn)?" Antwort: vergleichsbasierte Sortieralgorithmen haben eine Untergrenze von Ω(nlogn) Vergleichen (Entscheidungsbaum-Argument). Aber nicht-vergleichsbasierte Verfahren wie Counting Sort, Radix Sort oder Bucket Sort können O(n+k) bzw. O(n⋅d) erreichen, sofern der Wertebereich beschränkt ist. Quicksort und Bubblesort sind vergleichsbasiert; Mergesort ebenfalls.
Falle 3: "Stabilität ist immer wichtig"? Antwort: nein. Stabilität ist nur relevant, wenn nach mehreren Schlüsseln sortiert wird (z. B. erst nach Note, dann nach Name) oder wenn der Wert mit dem Sortier-Schlüssel verknüpfte Metadaten hat. Bei einfachem Sortieren nach einem eindeutigen Schlüssel spielt Stabilität keine Rolle.
Weiter im Tab "Interaktiv" siehst du alle drei Algorithmen live nebeneinander auf demselben Array.
Wähle eine Array-Größe und drück Start. Alle drei Algorithmen sortieren das gleiche Array parallel. Der Operation-Counter zählt Vergleiche und Schreiboperationen mit.
Probier folgendes:
Zufällig + n = 8: Unterschied klein, alle ähnlich
Zufällig + n = 32: Bubble bricht weg, Merge und Quick fast gleich auf
Sortiert + n = 16: Quicksort rutscht auf O(n²) ab und wird fast so langsam wie Bubblesort. Genau dafür gibt es randomisierte Pivots.
Lade Visualisierung...
Die Animation lügt nicht.Bubblesort schiebt jeden großen Wert mühsam Stück für Stück nach rechts. Mergesort baut sein Ergebnis aus immer größeren sortierten Blöcken zusammen. Quicksort partitioniert um Pivot-Punkte herum.
Was du beobachtet haben solltest:
Bei zufälligem n = 8: alle drei Algorithmen ähnlich schnell, der Unterschied ist hier noch klein
Bei zufälligem n = 32: Bubblesort fällt deutlich zurück (Quadratur dominiert), Merge und Quick gleichauf
Bei sortiertem n = 16: Quicksort braucht plötzlich fast so viele Vergleiche wie Bubblesort, weil die Lomuto-Partition mit letztem Element als Pivot in 0+(n-1) zerfällt. Genau dieser Worst Case ist der Grund warum reale Implementierungen Random-Pivot oder Median-of-Three nutzen.
Die Operation-Zähler bestätigen genau was die Big-O-Analyse vorhersagt: n2 wächst quadratisch, n⋅log2n fast linear, und Quicksort kann je nach Eingabe in beide Welten fallen.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Wenn du fertig bist: jetzt üben.
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Fachliche Qualität
A-TierZuletzt geprüft am 18.05.2026
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Klausur-ÜbersichtKomplette Übersicht: alle Tabs als linearer Text zum Lernen
▾
Alle Tabs der Lerneinheit (Übersicht · Interaktiv · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Teil 1·Erklärung
Übersicht
Drei Algorithmen im Vergleich
Bubblesort, und sind die drei klassischen Sortieralgorithmen, die in vielen Algorithmik-Klausuren gefragt werden. Sie unterscheiden sich in Komplexität, Speicherbedarf und Stabilität, daher musst du wissen welcher wann gewählt wird. Du lernst hier den der drei Verfahren in einer Tabelle (Best/Average/Worst Case, Speicher, Stabilität, In-Place), warum in der Praxis empfohlen wird (sonst Worst Case ), warum bei garantierter Worst-Case-Laufzeit oder Stabilitäts-Anforderung gewählt wird, warum den Quicksort-Worst-Case verschwindend unwahrscheinlich macht (Erwartungswert bleibt ), und warum Average aber Worst Case ist (degenerierte ).
Quicksort: O(n log n) Avg, O(n²) Worst, O(log n) Speicher, nicht stabil, in-place. Schnellster in der Praxis, kann degenerieren
In Klausuren wirst du oft gefragt: welcher Algorithmus bei dieser Eingabe / diesem Constraint?. Faustregel: Quicksort als Default, Mergesort wenn Stabilität oder garantierte O(n log n) gefordert, Bubblesort nie außer als Lehrbeispiel.
Wichtig zum Stack-Speicher bei Quicksort: der Rekursionsstack ist O(log n) im Average Case und O(n) im Worst Case (wenn der Pivot wiederholt schlecht gewählt wird und die Partition entartet). Mit Tail-Call-Optimierung und "rekursiv zuerst auf die kleinere Partition" lässt sich der Stack auf O(log n) Worst-Case begrenzen. Das ist nicht der Daten-Speicher (Array bleibt in-place), sondern der Stack-Speicher der Rekursion.
Entscheidungsmatrix für die Klausur
Anforderung
Wähle
Stabilität gefordert
Mergesort (oder Insertion Sort bei kleinem n)
Garantiert O(n log n) Worst Case
Mergesort oder Heapsort
In-Place, Speicher kritisch
Quicksort mit Random-Pivot oder Heapsort
Sehr kleines n (z. B. n < 30)
Insertion Sort (kleine Konstanten)
Daten teilweise sortiert
Timsort/Insertion Sort (adaptiv)
Klausur-Lehrbeispiel
Bubblesort (nie produktiv)
Wenn-dann-Kurzform für die Klausur:
Wenn ...
dann ...
Stabilität nötig
Mergesort
Speicher knapp, Stabilität egal
Quicksort mit Random-Pivot
Garantierte O(n log n) Worst Case
Mergesort oder Heapsort
Sehr kleines n (Mikro-Benchmark)
Insertion Sort
Daten fast sortiert
Timsort oder Insertion Sort
Lehr-Trace in Klausur
Bubblesort
Beispiel: Quicksort Schritt für Schritt auf [3, 1, 4, 1, 5]
Wir tracen einen ersten Lomuto-Partition-Schritt mit Pivot 5 (letztes Element):
j
arr[j]
≤ 5?
i nach
Array
0
3
ja
0
[3, 1, 4, 1, 5]
1
1
ja
1
[3, 1, 4, 1, 5]
2
4
ja
2
[3, 1, 4, 1, 5]
3
1
ja
3
[3, 1, 4, 1, 5]
Finaler Pivot-Tausch: arr[i+1] = arr[4], hier 5 mit 5 → keine Änderung. Pivot-Index = 4. Komplette Partition liefert [3, 1, 4, 1, 5], alle Werte links sind ≤ 5. Rekursive Calls dann auf [3, 1, 4, 1] und auf den leeren rechten Bereich. Beobachtung: schlecht gewählter Pivot (Maximum) führt zu 0+(n-1)-Split, klassischer Worst-Case-Auslöser bei sortiertem Input.
Wann welcher?
Bubblesort, wann wählen? Nur didaktisch. Für jedes praktische n > 50 ist er unbrauchbar (Quadratur kostet zu viel). Warum nicht? Average und Worst Case beide O(n²), ~n²/2 Vergleiche. Klausurfalle: "Bubblesort ist immer O(n²)", falsch, mit Early-Exit ist Best Case O(n).
Mergesort, wann wählen? Wenn Stabilität gefordert oder garantierteO(n log n) Worst-Case-Laufzeit nötig (z. B. Echtzeit-Anwendungen). Warum nicht? Wenn Speicher kritisch ist, weil typisch O(n) Hilfsarray nötig. Klausurfalle: Stabilität-Beweis "warum ist Mergesort stabil?", wegen ≤ im Merge-Schritt, gleiche Werte aus L vor gleichen aus R.
Quicksort, wann wählen? Wenn Speicher knapp und Stabilität egal. In der Praxis oft sehr schnell wegen guter Cache-Lokalität, kann aber ohne Absicherung degenerieren. Warum nicht? Bei sortiertem Input mit naiver Pivot-Wahl → O(n²). Klausurfalle: "Quicksort ist immer in-place", Array ja, Rekursionsstack aber bis O(n) tief.
Praxis außerhalb der Algorithmik-Quellen (optional, nicht durch CLRS/Sedgewick/Ottmann gedeckt):
Niemand schreibt selbst Sortierfunktionen für die Praxis. Standard-Bibliotheken haben hochoptimierte Hybride:
JavaArrays.sort(): Timsort für Objekte (Mergesort + Insertion Sort), Dual-Pivot Quicksort für primitive Typen. Quelle: OpenJDK-Doku.
Pythonsorted(): Timsort. Quelle: CPython-Quelltext und Timsort-Originalbeschreibung von Tim Peters.
Aber im Kopf haben muss man die Klassiker, sie tauchen in jeder Algorithmik-Klausur auf.
Häufige Klausurfallen im Vergleich
Falle 1: "Welcher Algorithmus ist immer am schnellsten?" Antwort: keiner. Quicksort ist im Average Case oft am schnellsten in der Praxis, kann aber auf O(n²) degenerieren. Mergesort garantiert O(n log n), braucht aber mehr Speicher. Bei kleinem n sind Insertion Sort oder sogar Bubblesort durch geringere Konstanten konkurrenzfähig. Die richtige Antwort hängt immer von Eingabegröße, Eingabestruktur und Speicheranforderung ab.
Falle 2: "Sortieren ist immer O(n log n)?" Antwort: vergleichsbasierte Sortieralgorithmen haben eine Untergrenze von Ω(n log n) Vergleichen (Entscheidungsbaum-Argument). Aber nicht-vergleichsbasierte Verfahren wie Counting Sort, Radix Sort oder Bucket Sort können O(n + k) bzw. O(n · d) erreichen, sofern der Wertebereich beschränkt ist. Quicksort und Bubblesort sind vergleichsbasiert; Mergesort ebenfalls.
Falle 3: "Stabilität ist immer wichtig"? Antwort: nein. Stabilität ist nur relevant, wenn nach mehreren Schlüsseln sortiert wird (z. B. erst nach Note, dann nach Name) oder wenn der Wert mit dem Sortier-Schlüssel verknüpfte Metadaten hat. Bei einfachem Sortieren nach einem eindeutigen Schlüssel spielt Stabilität keine Rolle.
Weiter im Tab "Interaktiv" siehst du alle drei Algorithmen live nebeneinander auf demselben Array.
Teil 2·Visualisierung / Interaktiv
Interaktiv
Live-Vergleich
Wähle eine Array-Größe und drück Start. Alle drei Algorithmen sortieren das gleiche Array parallel. Der Operation-Counter zählt Vergleiche und Schreiboperationen mit.
Probier folgendes:
Zufällig + n = 8: Unterschied klein, alle ähnlich
Zufällig + n = 32: Bubble bricht weg, Merge und Quick fast gleich auf
Sortiert + n = 16: Quicksort rutscht auf O(n²) ab und wird fast so langsam wie Bubblesort. Genau dafür gibt es randomisierte Pivots.
Interaktive Visualisierung
Animiert mehrere Sortier-Algorithmen parallel mit Vergleichs- und Tausch-Counter.
Die Animation lügt nicht.Bubblesort schiebt jeden großen Wert mühsam Stück für Stück nach rechts. Mergesort baut sein Ergebnis aus immer größeren sortierten Blöcken zusammen. Quicksort partitioniert um Pivot-Punkte herum.
Was du beobachtet haben solltest:
Bei zufälligem n = 8: alle drei Algorithmen ähnlich schnell, der Unterschied ist hier noch klein
Bei zufälligem n = 32: Bubblesort fällt deutlich zurück (Quadratur dominiert), Merge und Quick gleichauf
Bei sortiertem n = 16: Quicksort braucht plötzlich fast so viele Vergleiche wie Bubblesort, weil die Lomuto-Partition mit letztem Element als Pivot in 0+(n-1) zerfällt. Genau dieser Worst Case ist der Grund warum reale Implementierungen Random-Pivot oder Median-of-Three nutzen.
Die Operation-Zähler bestätigen genau was die Big-O-Analyse vorhersagt: n² wächst quadratisch, n · log₂ n fast linear, und Quicksort kann je nach Eingabe in beide Welten fallen.
Teil 3·Quiz / Klausurfragen
Quiz
Klausurfragen mit Lösungen (6)
F1.Welcher der drei Algorithmen ist nicht stabil?
Antwort: Quicksort
Erklärung: Quicksort ist nicht stabil: bei der Partitionierung können gleiche Werte ihre relative Reihenfolge verlieren. Bubblesort und Mergesort sind beide stabil.
F2.Du sortierst eine Liste von Studenten zuerst nach Name, dann nach Note. Welcher Algorithmus garantiert dass die Endreihenfolge bei gleicher Note alphabetisch nach Name bleibt?
Antwort: Mergesort
Erklärung: Klausur-Trick beim mehrstufigen Sortieren: zuerst nach dem **sekundären** Schlüssel (Name) sortieren, dann **stabil** nach dem **primären** Schlüssel (Note). Stabilität sorgt dafür dass gleiche Note ihre Name-Reihenfolge behält. Mergesort ist stabil; Standard-In-Place-Quicksort ist normalerweise nicht stabil (stabile Varianten gibt es, sind aber nicht die Klausur-Standardannahme) und würde die alphabetische Reihenfolge bei gleicher Note zerstören. Alternative: einmaliges Sortieren mit Comparator (note, name), dann ist Stabilität nicht nötig.
F3.Welcher Algorithmus wird in Java's Arrays.sort() für Objekt-Arrays verwendet?
Antwort: Timsort
Erklärung: Java's Arrays.sort() für Objekte nutzt Timsort, eine Kombination aus Mergesort und Insertion Sort. Für primitive Typen wird Dual-Pivot Quicksort verwendet, weil dort Stabilität egal ist.
F4.Eine verschachtelte Schleife läuft n × n Mal. Wie oft wird der innere Block bei n = 1000 ausgeführt?
Antwort: 1000000
Erklärung: n² bei n = 1000 ist 1.000 × 1.000 = 1.000.000. Genau deshalb skaliert Bubblesort schlecht: bei einer Million Einträgen sind das 10¹² Operationen, also Stunden statt Millisekunden.
Typ: Zahlen-Eingabe
F5.Was ist der größte Vorteil von Mergesort gegenüber Quicksort?
Antwort: Mergesort hat garantiertes O(n log n) und ist stabil
Erklärung: Mergesort hat zwei klare Vorteile: garantierte O(n log n) ohne Worst-Case-Risiko, und Stabilität. Quicksort ist im Average Case meist schneller (Cache-Lokalität, in-place), aber ohne Absicherung kann er auf O(n²) abrutschen.
F6.Welche Sortieralgorithmen haben eine Worst-Case-Komplexität von O(n log n)?
Richtige Antworten: Mergesort; Heapsort; Timsort
Erklärung: Mergesort, Heapsort und Timsort sind alle garantiert O(n log n) auch im Worst Case. Bubblesort ist O(n²), Quicksort ist im Worst Case O(n²) (nur Average O(n log n)). Klausur-Klassiker zur Worst-Case-Garantie.
