Sortieralgorithmen: Bubblesort, Quicksort und Mergesort im Vergleich
Sortierverfahren mit ihren Laufzeiten vergleichen und einen Durchlauf per Hand ausführen: Beides sind Klassiker der Fachinformatiker-Prüfung (besonders Anwendungsentwicklung). Hier bekommst du beides kompakt.
🃏 Zuerst kurz zur O-Notation: Sie beschreibt nur, wie stark der Aufwand wächst, wenn die Datenmenge größer wird, nicht die genaue Zeit. O(n²) heißt: doppelt so viele Elemente → viermal so viel Arbeit (schlecht bei großen Mengen). O(n log n) wächst viel langsamer und ist deshalb bei großen Datenmengen klar besser. Denk an Karten sortieren: Insertionsort ist genau das, was du intuitiv tust: Du nimmst eine Karte und steckst sie an die richtige Stelle in deiner Hand.
Die wichtigsten Verfahren im Vergleich
| Verfahren | Best Case | Average | Worst Case | Stabil? |
|---|---|---|---|---|
| Bubblesort | O(n) | O(n²) | O(n²) | ja |
| Insertionsort | O(n) | O(n²) | O(n²) | ja |
| Selectionsort | O(n²) | O(n²) | O(n²) | nein |
| Quicksort | O(n log n) | O(n log n) | O(n²) | nein |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | ja |
Stabil heißt: Gleiche Werte behalten ihre ursprüngliche Reihenfolge. Das ist wichtig, wenn nach mehreren Kriterien nacheinander sortiert wird (ein beliebtes Prüfungsdetail).
Bubblesort per Hand: ein Durchlauf
Ausgangsfolge: 5, 2, 4, 1. Bubblesort vergleicht immer zwei Nachbarn und tauscht, wenn sie falsch herum stehen.
Vergleich 5|2 → tauschen: 2, 5, 4, 1
Vergleich 5|4 → tauschen: 2, 4, 5, 1
Vergleich 5|1 → tauschen: 2, 4, 1, 5
Nach dem ersten Durchlauf steht das größte Element ganz hinten, es ist wie eine Blase nach oben „aufgestiegen". Genau diese Eigenschaft wird in Prüfungen gern abgefragt.
Quicksort und Mergesort in Kürze
Quicksort wählt ein Pivot-Element, teilt die Folge in „kleiner" und „größer" und sortiert die Teile rekursiv. Im Schnitt sehr schnell, aber bei ungünstigem Pivot (z. B. bereits sortierte Folge) degradiert er zu O(n²). Mergesort teilt die Folge immer in der Mitte, sortiert beide Hälften rekursiv und verschmilzt sie (Merge). Er garantiert O(n log n), braucht dafür aber zusätzlichen Speicher.
💡 Prüfungstipp, das musst du sicher wissen: Mergesort = immer O(n log n) und stabil (aber extra Speicher). Quicksort = im Schnitt schnell, aber Worst Case O(n²) bei schon sortierter Folge. Bubble-/Insertion-/Selectionsort = einfach, aber O(n²). Diese drei Fakten decken die meisten Fragen ab.
⚠️ Häufige Fehler in der Prüfung:
- Quicksort für „immer schnell" halten. Sein Worst Case ist O(n²), nicht O(n log n).
- „Stabil" mit „schnell" verwechseln. Stabil heißt nur: gleiche Werte behalten ihre Reihenfolge.
- Bei Bubblesort einen Durchlauf falsch zählen. Pro Durchlauf wandert ein größtes Element ans Ende, nicht die halbe Folge.
- O(n log n) und O(n²) verwechseln: n log n wächst deutlich langsamer und ist bei großen Datenmengen besser.
Jetzt selbst testen
Beantworte die Fragen und bekomme sofort Feedback, so viele Versuche du willst.
Welches Verfahren ist stabil UND garantiert O(n log n) im Worst Case?
Was gilt nach dem ersten kompletten Durchlauf von Bubblesort?
Bei welcher Eingabe zeigt Quicksort (Pivot = letztes Element) seinen Worst Case?
Was bedeutet 'stabiles' Sortierverfahren?
Welche durchschnittliche Laufzeit hat Bubblesort?
Häufige Fragen
Welcher Sortieralgorithmus ist der schnellste?
Im Durchschnitt gehört Quicksort mit O(n log n) zu den schnellsten Verfahren. Mergesort garantiert O(n log n) sogar im schlechtesten Fall, braucht aber zusätzlichen Speicher. Einfache Verfahren wie Bubblesort liegen bei O(n²) und sind nur für kleine Datenmengen geeignet.
Was bedeutet ein stabiles Sortierverfahren?
Ein Verfahren ist stabil, wenn Elemente mit gleichem Sortierwert ihre ursprüngliche Reihenfolge behalten. Bubblesort, Insertionsort und Mergesort sind stabil, Selectionsort und Quicksort in der Standardform nicht.
Wie funktioniert Bubblesort?
Bubblesort vergleicht wiederholt benachbarte Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge stehen. Nach jedem Durchlauf steht das größte verbleibende Element am Ende, es steigt wie eine Blase auf. Laufzeit im Normalfall O(n²).
Wann hat Quicksort seinen Worst Case?
Wenn das Pivot-Element wiederholt ungünstig gewählt wird, klassisch bei einer bereits sortierten Folge und Pivot am Rand. Dann zerfällt die Aufteilung in extrem ungleiche Teile und die Laufzeit wird O(n²).
Verwandte Themen
Algorithmen interaktiv trainieren
In der Lernarena führst du Sortierdurchläufe Schritt für Schritt aus: mit sofortigem Feedback, echten IHK-Prüfungsaufgaben und einem KI-Tutor. Kostenlos starten, direkt üben.