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.
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.
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?
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.