Bubblesort, Mergesort und Quicksort live nebeneinander. Übersichtstabelle, interaktiver Visualizer und Klausur-Quiz, das die Unterschiede festigt.
Bubblesort, Mergesort und Quicksort sind die drei klassischen Sortieralgorithmen die in jeder Klausur gefragt werden. Sie unterscheiden sich in Komplexität, Speicherbedarf und Stabilität, daher musst du wissen welcher wann gewählt wird.
Die Kernunterschiede in einer Tabelle:
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.
| Algorithmus | Avg | Worst | Speicher | Stabil? | In-Place? |
|---|---|---|---|---|---|
| Bubblesort | O(n²) | O(n²) | O(1) | ✅ | ✅ |
| Mergesort | O(n log n) | O(n log n) | O(n) | ✅ | ❌ |
| Quicksort | O(n log n) | O(n²) | O(log n) | ❌ | ✅ |
Niemand schreibt selbst Sortierfunktionen für die Praxis. Standard-Bibliotheken haben hochoptimierte Hybride:
Arrays.sort(): Timsort für Objekte (Mergesort + Insertion Sort), Dual-Pivot Quicksort für primitive Typensorted(): Timsortstd::sort: Introsort (Quicksort + Heapsort als Fallback)Aber im Kopf haben muss man die Klassiker, sie tauchen in jeder Algorithmik-Klausur auf.
Weiter im Tab "Interaktiv" siehst du alle drei Algorithmen live nebeneinander auf demselben Array.
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).
Bubblesort, Mergesort und sind die drei klassischen Sortieralgorithmen die in jeder Klausur gefragt werden. Sie unterscheiden sich in Komplexität, Speicherbedarf und Stabilität, daher musst du wissen welcher wann gewählt wird.
Wie wächst der Aufwand eines Algorithmus mit der Eingabe-Größe? Konstant, linear, quadratisch, und wann macht der Unterschied wirklich was aus?
Der simpelste Suchalgorithmus: jedes Element prüfen bis Treffer oder Ende. Funktioniert auf jedem Array, sortiert oder nicht. O(n) im Worst Case.
Halbiere den Suchraum bei jedem Schritt. O(log n) statt O(n): bei einer Milliarde Einträgen reichen 30 Vergleiche. Voraussetzung: sortiertes Array.
Die Kernunterschiede in einer Tabelle:
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.
| Algorithmus | Avg | Worst | Speicher | Stabil? | In-Place? |
|---|---|---|---|---|---|
| Bubblesort | O(n²) | O(n²) | O(1) | ✅ | ✅ |
| Mergesort | O(n log n) | O(n log n) | O(n) | ✅ | ❌ |
| Quicksort | O(n log n) | O(n²) | O(log n) | ❌ | ✅ |
Niemand schreibt selbst Sortierfunktionen für die Praxis. Standard-Bibliotheken haben hochoptimierte Hybride:
Arrays.sort(): Timsort für Objekte (Mergesort + Insertion Sort), Dual-Pivot Quicksort für primitive Typensorted(): Timsortstd::sort: Introsort (Quicksort + Heapsort als Fallback)Aber im Kopf haben muss man die Klassiker, sie tauchen in jeder Algorithmik-Klausur auf.
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:
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.
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.
Klausurfragen mit Lösungen (6)
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.
Antwort: Mergesort
Erklärung: Bei mehrfachem Sortieren brauchst du Stabilität: gleiche Schlüssel müssen ihre Reihenfolge behalten. Mergesort ist stabil, Quicksort nicht. Quicksort würde die alphabetische Reihenfolge bei gleicher Note zerstören.
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.
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
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.
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.
Typ: Multi-Select