Cocktail Shaker Sort

Cocktail shaker sort extends bubble sort by performing passes in both directions. One pass moves the largest element to the end, and the next pass moves the smallest element to the beginning. This reduces the number of passes needed compared to standard bubble sort.

It is also called bidirectional bubble sort.

Problem

Given a sequence $A$ of length $n$ , reorder it such that

A[0] \le A[1] \le \cdots \le A[n-1]

Algorithm

Maintain two boundaries, left and right. Sweep forward to push the maximum to the right boundary, then sweep backward to push the minimum to the left boundary. Shrink the boundaries after each pair of passes.

cocktail_shaker_sort(A):
    left = 0
    right = length(A) - 1
    while left < right:
        swapped = false

        for i from left to right - 1:
            if A[i] > A[i + 1]:
                swap(A[i], A[i + 1])
                swapped = true
        right = right - 1

        for i from right downto left + 1:
            if A[i - 1] > A[i]:
                swap(A[i - 1], A[i])
                swapped = true
        left = left + 1

        if swapped == false:
            break

Example

Let

A = [3, 0, 2, 5, 1]

Forward pass:

step	result
swap (3,0)	[0,3,2,5,1]
swap (3,2)	[0,2,3,5,1]
keep (3,5)	[0,2,3,5,1]
swap (5,1)	[0,2,3,1,5]

Backward pass:

step	result
swap (3,1)	[0,2,1,3,5]
swap (2,1)	[0,1,2,3,5]

Sorted result:

[0,1,2,3,5]

Correctness

Each forward pass ensures the maximum element moves to its correct position at the right boundary. Each backward pass ensures the minimum element moves to its correct position at the left boundary. The unsorted region shrinks from both sides, and eventually the entire array becomes sorted.

Complexity

case	comparisons	time
best	$n$	$O(n)$
worst	$\frac{n(n-1)}{2}$	$O(n^2)$
average	$\approx \frac{n^2}{2}$	$O(n^2)$

Space complexity:

O(1)

Properties

stable
in-place
slightly better than bubble sort for some inputs

When to Use

This algorithm performs better than standard bubble sort when small elements are near the end or large elements are near the beginning. It reduces unnecessary passes in such cases, though it remains inefficient for large datasets.

Implementation

def cocktail_shaker_sort(a):
    left = 0
    right = len(a) - 1

    while left < right:
        swapped = False

        for i in range(left, right):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        right -= 1

        for i in range(right, left, -1):
            if a[i - 1] > a[i]:
                a[i - 1], a[i] = a[i], a[i - 1]
                swapped = True
        left += 1

        if not swapped:
            break

    return a

func CocktailShakerSort[T constraints.Ordered](a []T) {
    left := 0
    right := len(a) - 1

    for left < right {
        swapped := false

        for i := left; i < right; i++ {
            if a[i] > a[i+1] {
                a[i], a[i+1] = a[i+1], a[i]
                swapped = true
            }
        }
        right--

        for i := right; i > left; i-- {
            if a[i-1] > a[i] {
                a[i-1], a[i] = a[i], a[i-1]
                swapped = true
            }
        }
        left++

        if !swapped {
            break
        }
    }
}