Cocktail Shaker Sort
Passes through the array in both directions, pushing large values to the end and small values to the start each round.
How it works
Cocktail shaker sort is bubble sort that runs both ways. A forward pass carries the largest value to the right end, just like bubble sort. Then a backward pass carries the smallest value to the left end. The unsorted part shrinks from both sides, and the sort stops as soon as a pass makes no swaps.
Going both ways fixes bubble sort's weak spot, the "turtles": small values near the end that bubble sort can only move one step left per pass. One backward pass carries a turtle all the way to the front.
Implementations
function cocktailShakerSort(array) {
let start = 0;
let end = array.length - 1;
let swapped = true;
while (swapped) {
swapped = false;
for (let i = start; i < end; i++) {
if (array[i] > array[i + 1]) {
[array[i], array[i + 1]] = [array[i + 1], array[i]];
swapped = true;
}
}
if (!swapped) break;
end--;
swapped = false;
for (let i = end - 1; i >= start; i--) {
if (array[i] > array[i + 1]) {
[array[i], array[i + 1]] = [array[i + 1], array[i]];
swapped = true;
}
}
start++;
}
return array;
}
def cocktail_shaker_sort(array):
a = list(array)
start, end = 0, len(a) - 1
swapped = True
while swapped:
swapped = False
for i in range(start, end):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
swapped = True
if not swapped:
break
end -= 1
swapped = False
for i in range(end - 1, start - 1, -1):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
swapped = True
start += 1
return a
Complexity
| Case | Time | When |
|---|---|---|
| Best | O(n) | Already sorted: one pass with no swaps |
| Average | O(n²) | Random order |
| Worst | O(n²) | Sorted in reverse |
| Extra space | Why |
|---|---|
| O(1) | It only swaps neighbours in place, using a few loop variables |