Cocktail Shaker Sort
Im folgenden sehen wir, wie der primitive Ansatz des BubbleSort
mit wenigen Optimierungen dramatisch verbessert werden kann:
Legende:
rosa: größerer Vergleichspartner
rot: kleinerer Vergleichspartner
blau: bereits sortierter Teil
Der "einfache" BubbleSort wurde in zwei Schritten
verbessert:
- Nach jedem Durchlauf ("bubble up") wird abgefragt, ob noch zwei
Elemente vertauscht wurden -> swapped = = false?
Falls nicht, ist die Liste bereits sortiert -> Abbruch
- Nach jedem Durchlauf von unten nach oben ("bubble up") erfolgt
ein Durchlauf in Richtung von oben nach unten ("bubble
down").
Das Ergebnis ist der sogenannte "Cocktail Shaker Sort" (resp.
"verbesserter" oder "bidirektionaler Bubble Sort"). Seine Laufzeit
ist im ungünstigsten Fall ("worst case") immer noch
quadratisch; aber bei fast sortierten Reihungen ("best case") wird
lineare Laufzeit erreicht.
Links zu Cocktail Shaker Sort:
zurück zur Startseite
