Die wichtigsten Verfahren im Vergleich
Die Tabelle zeigt die Laufzeit im besten, mittleren und schlechtesten Fall. In Prüfungsaufgaben stehen dafür oft die englischen Begriffe Best Case, Average Case und Worst Case.
| Verfahren | Bester Fall | Mittlerer Fall | Schlechtester Fall | 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.
Start: 5, 2, 4, 1
5 und 2 vergleichen, tauschen: 2, 5, 4, 1
5 und 4 vergleichen, tauschen: 2, 4, 5, 1
5 und 1 vergleichen, tauschen: 2, 4, 1, 5Nach 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.
Häufige Fehler in der Prüfung
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) auch im schlechtesten Fall?
Was gilt nach dem ersten kompletten Durchlauf von Bubblesort?
Bei welcher Eingabe zeigt Quicksort (Pivot = letztes Element) seinen schlechtesten Fall?
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 tritt bei Quicksort der schlechteste Fall ein?
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, Aufgaben im IHK-Stil und der KI-Tutorin Ada.