Cocktail Sort
Bubble Sort, das in jedem Durchgang die Richtung wechselt und so beide Enden zugleich sortiert.
- Vergleiche 0
- Tauschvorgänge 0
- sortierte Indizes 0
- Vergleich
- Tausch
- sortiert
Pseudocode
1 lo = 0; hi = n - 1; swapped = true
2 while swapped
3 swapped = false
4 for j from lo to hi - 1: if a[j] > a[j+1] swap; swapped = true
5 hi -= 1
6 if not swapped: break
7 for j from hi to lo + 1: if a[j-1] > a[j] swap; swapped = true
8 lo += 1
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Cocktail Sort (auch Shaker Sort oder bidirektionales Bubble Sort) ist eine Variante des Bubble Sort. Im Unterschied zum klassischen Bubble Sort, der jeden Durchlauf von links nach rechts macht, wechselt Cocktail Sort die Richtung: erst ein Vorwärts-Pass, der das jeweils größte Element nach rechts schiebt, dann ein Rückwärts-Pass, der das kleinste Element nach links zieht. Dadurch werden die sogenannten Schildkröten, also kleine Elemente, die am Ende des Arrays stehen und sich in jedem Bubble-Durchgang nur um eine Position vorwärts bewegen, deutlich schneller an ihren Platz transportiert. Die Laufzeit bleibt im Worst Case quadratisch (O(n²)) wie bei Bubble Sort, im Best Case bei bereits sortierten Daten linear (O(n)). Der Speicherbedarf ist konstant (O(1)) und der Algorithmus ist stabil.
Komplexität
- Best Case
O(n) - Average Case
O(n^2) - Worst Case
O(n^2) - Zusatz-Speicher
O(1)
Wann verwenden?
In der Praxis selten verwendet, weil Insertion Sort auf nahezu sortierten Daten ähnliche Vorteile bietet und schneller ist. Cocktail Sort dient hauptsächlich als Lehrbeispiel, um zu zeigen, wie eine einfache Anpassung an Bubble Sort die Performance bei bestimmten Eingaben deutlich verbessern kann.