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.

Wir zeigen im folgenden, dass die Laufzeit im schlechtesten Fall immer noch quadratisch ist. Der schlechteste Fall tritt (genau wie bei BubbleSort) dann ein, wenn die gegebene Reihung umgekehrt sortiert ist¹, also arr=(n,n-1,...3,2,1). Nach n-1 Vergleichen und n-1 Vertauschungen ist die erste "bubble-up" Phase beendet, und das Element n landet an der gewünschten Position; die erste "bubble-down" Phase benötigt weitere n-2 Vergleiche und n-2 Vertauschungen, und das Element 1 landet an der gewünschten Position. Die übrigen n-2 Elemente sind immer noch umgekehrt sortiert. Nach je einem "bubble-up" und "bubble-down" sind die Variablen "start" um 1 erhöht und die Variable "ende" um 1 verringert. Die Teilreihung, die vom Cocktail Shaker Sort ab jetzt betrachtet wird, ist also gegenüber der ursprünglichen Reihung um 2 geschrumpft, und hat noch die Länge n-2.

Bezeichnet V(n) die Anzahl der Vergleiche, die Cocktail Shaker Sort für eine umgekehrt sortierte Reihung benönigt, so erhalten wir:
V(1) = 0
V(2) = 1
Für n > 1 :
V(n) = (n-1) + (n-2) + V(n-2)
    = n-1 + n-2 + n-3 + n-4 + V(n-4)
    = n-1 + n-2 + n-3 + n-4 + ... + n-(n-2) + n-(n-1) + V(n-(n-1))
    = n-1 + n-2 + n-3 + n-4 + ... + 2 + 1 + V(1)
    = n(n-1)/2.

Fußnoten

¹Streng genommen müssen wir auch beweisen, dass die umgekehrt sortierte Reihung der schlechteste Fall ist, aber diesen Nachweis (und andere Details) lassen wir hier weg.

Links zu Cocktail Shaker Sort:

zurück zur Startseite