# Cocktail Shaker Sort

# 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.

```id="c1x8q4"
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

```id="b7k2n9"
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
```

```id="m5q8t1"
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
        }
    }
}
```