Cocktail Shaker Sort
See bubble sort pass in both directions, pushing large values right and small values left 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.
When to use it
It usually beats bubble sort by a small margin, especially when a few small values sit near the end. It is still quadratic, so it's mainly useful for learning how small changes to an algorithm affect its behaviour.
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 |
Like bubble sort, it only swaps neighbours in place, so it uses O(1) extra space and is stable.
Implementations
function cocktailShakerSort(array) {
const a = [...array];
let start = 0;
let end = a.length - 1;
let swapped = true;
while (swapped) {
swapped = false;
for (let i = start; i < end; i++) {
if (a[i] > a[i + 1]) {
[a[i], a[i + 1]] = [a[i + 1], a[i]];
swapped = true;
}
}
if (!swapped) break;
end--;
swapped = false;
for (let i = end - 1; i >= start; i--) {
if (a[i] > a[i + 1]) {
[a[i], a[i + 1]] = [a[i + 1], a[i]];
swapped = true;
}
}
start++;
}
return a;
}
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
#include <utility>
#include <vector>
std::vector<int> cocktailShakerSort(std::vector<int> a) {
int start = 0;
int end = static_cast<int>(a.size()) - 1;
bool swapped = true;
while (swapped) {
swapped = false;
for (int i = start; i < end; i++) {
if (a[i] > a[i + 1]) {
std::swap(a[i], a[i + 1]);
swapped = true;
}
}
if (!swapped) break;
end--;
swapped = false;
for (int i = end - 1; i >= start; i--) {
if (a[i] > a[i + 1]) {
std::swap(a[i], a[i + 1]);
swapped = true;
}
}
start++;
}
return a;
}