Cocktail Shaker Sort

Cocktail Shaker Sort, also known as Bidirectional Bubble Sort, is a variation of Bubble Sort that sorts in both directions. It traverses the array from left to right, then right to left, which can be more efficient than standard Bubble Sort for certain data patterns.

Complexity Analysis

Best Case

O(n)

Average Case

O(n²)

Worst Case

O(n²)

Space Complexity

O(1)

function cocktailShakerSort(arr) {
    let start = 0;
    let end = arr.length - 1;
    let swapped = true;

    while (swapped) {
        swapped = false;

        // Forward pass (left to right)
        for (let i = start; i < end; i++) {
            if (arr[i] > arr[i + 1]) {
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                swapped = true;
            }
        }
        end--;

        // If no swaps occurred, array is sorted
        if (!swapped) break;

        swapped = false;

        // Backward pass (right to left)
        for (let i = end; i > start; i--) {
            if (arr[i] < arr[i - 1]) {
                [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
                swapped = true;
            }
        }
        start++;
    }
    return arr;
}

How Cocktail Shaker Sort Works

Cocktail Shaker Sort improves upon Bubble Sort by traversing the array in both directions. It behaves like a cocktail shaker mixing ingredients - first one way, then the other.

Algorithm Steps:

  1. Set boundaries: start at beginning, end at array end
  2. Forward Pass: Bubble sort from left to right
  3. Move largest unsorted element to its correct position
  4. Reduce the end boundary (exclude sorted element)
  5. Backward Pass: Bubble sort from right to left
  6. Move smallest unsorted element to its correct position
  7. Reduce the start boundary (exclude sorted element)
  8. Repeat until no more swaps occur

Advantages over Bubble Sort:

  • Bidirectional: Works in both directions for better element movement
  • Fewer iterations: Often requires fewer passes than standard Bubble Sort
  • Better for certain patterns: More efficient when small elements are at the end
  • Same simplicity: Still easy to understand and implement

When It's Most Effective:

  • Turtles and rabbits: When small elements are at the end (rabbits)
  • Partially sorted arrays: Benefits from bidirectional movement
  • Educational purposes: Demonstrates bidirectional sorting concept

Performance Characteristics:

  • Best Case: O(n) when array is already sorted
  • Worst Case: O(n²) when array is reverse sorted
  • Improvement: Usually 30-50% fewer comparisons than Bubble Sort
  • Adaptive: Performance improves with partially sorted data