Cocktail Shaker Sort
A bidirectional variation of bubble sort that traverses the list in both directions alternately, improving performance on certain types of data.
Visualization
Details
Analogy
Imagine a cocktail shaker moving back and forth. Just as a bartender shakes a cocktail up and down to mix ingredients, this algorithm 'shakes' the array by sorting from left to right, then right to left, repeatedly. This bidirectional approach settles both large and small elements faster than one-directional bubble sort.
Purpose
To sort an array more efficiently than standard bubble sort by alternating between forward and backward passes. Each forward pass moves the largest unsorted element to its final position, while each backward pass moves the smallest unsorted element to the beginning.
Use Cases
More efficient than bubble sort for lists with elements that need to move long distances, especially when small elements are at the end (the 'rabbit and turtle' problem). Useful for educational purposes to demonstrate algorithm optimization. Sometimes used in embedded systems where simplicity is important but better performance than bubble sort is needed.
Algorithm Steps
function cocktailShakerSort(array):
start = 0
end = length(array) - 1
swapped = true
while swapped:
swapped = false
for i = start to end - 1:
if array[i] > array[i + 1]:
swap(array[i], array[i + 1])
swapped = true
if not swapped: break
end = end - 1
swapped = false
for i = end - 1 down to start:
if array[i] > array[i + 1]:
swap(array[i], array[i + 1])
swapped = true
start = start + 1
return array
Explanation
What's Happening?
Initial array: [5, 1, 4, 2, 8, 0, 2]. We'll sort by alternating forward and backward passes.
Code Implementation
def cocktail_shaker_sort(arr):
n = len(arr)
start = 0
end = n - 1
swapped = True
while swapped:
swapped = False
# Forward pass
for i in range(start, end):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped = True
if not swapped:
break
end -= 1
swapped = False
# Backward pass
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