Cocktail Sort — Bubble Sort learned to walk BACKWARDS and it changes everything

Описание: Cocktail Sort — Bubble Sort learned to walk BACKWARDS and it changes everything | Green-to-orange O(n²) bidirectional visualization


See how this bidirectional variant of Bubble Sort sweeps forward through the array bubbling the largest value to the end, then immediately sweeps backward pulling the smallest value to the front. Gradient elements flow from green to orange as they rock back and forth like a cocktail shaker — the sorted boundaries closing in from both sides simultaneously. Each complete cycle tightens the unsorted window from both ends, trapping elements in their final positions twice as efficiently as one-way bubbling.


Used for teaching bidirectional traversal and understanding how small optimizations can drastically reduce unnecessary passes. Cocktail Sort eliminates the "turtle" problem where small values stuck at the end take forever to reach the front. By sweeping in both directions, turtles and rabbits are handled equally. Still O(n²) worst case, but performs significantly fewer passes than Bubble Sort on nearly-sorted data. Stable, in-place, and adaptive — terminates early when no swaps occur in a full forward-backward cycle.

📝 PSEUDOCODE:

procedure cocktailSort(A):
swapped = true
start = 0
end = length(A) - 1

while swapped:
swapped = false

// Forward pass (left to right)
for i = start to end - 1:
if A[i] ≻ A[i+1]:
swap(A[i], A[i+1])
swapped = true
end -= 1

if not swapped:
break

swapped = false

// Backward pass (right to left)
for i = end - 1 down to start:
if A[i] ≻ A[i+1]:
swap(A[i], A[i+1])
swapped = true
start += 1


🐍 PYTHON:

def cocktail_sort(arr):
n = len(arr)
swapped = True
start, end = 0, n - 1

while swapped:
swapped = False
for i in range(start, end):
if arr[i] ≻ arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped = True
end -= 1

if not swapped:
break

swapped = False
for i in range(end - 1, start - 1, -1):
if arr[i] ≻ arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped = True
start += 1

return arr


🔗 Want to see more clever variations on classic algorithms? Check out our other algorithm visualizations to explore how small tweaks create big improvements. Subscribe and hit the bell to watch sorting algorithms evolve from simple to smart!


💚🧡 Subscribe for daily algorithm visualizations