Cocktail Sort

Bubble sort that shakes in both directions, like a bartender mixing a cocktail.

0 elements

SpdSize50

>Ready — Cocktail Sort

Code

let start = 0;
let end = length - 1;
let swapped = true;
while (swapped) {
  swapped = false;
  for (let i = start; i < end; i++) {
    if (compare(i, i + 1)) {
      swap(i, i + 1);
      swapped = true;
    }
  }
  end--;
  if (!swapped) break;
  swapped = false;
  for (let i = end; i > start; i--) {
    if (compare(i - 1, i)) {
      swap(i - 1, i);
      swapped = true;
    }
  }
  start++;
}

let start = 0;
let end = length - 1;
let swapped = true;
while (swapped) {
  swapped = false;
  for (let i = start; i < end; i++) {
    if (compare(i, i + 1)) {
      swap(i, i + 1);
      swapped = true;
    }
  }
  end--;
  if (!swapped) break;
  swapped = false;
  for (let i = end; i > start; i--) {
    if (compare(i - 1, i)) {
      swap(i - 1, i);
      swapped = true;
    }
  }
  start++;
}

Analysis

BEST O(n)

AVG O(n²)

WORST O(n²)

SPACE O(1)

STABLE

Cocktail Shaker Sort (a.k.a. Bidirectional Bubble Sort) is a variation of Bubble Sort that traverses the array in both directions alternately. The forward pass bubbles the largest element to the end, then the backward pass bubbles the smallest to the beginning. It’s slightly better than Bubble Sort for arrays where small elements are stuck at the end ("turtles"), but still O(n²).

Edit in playground→