Cocktail sort, just like Bubble sort, works by iterating through the list, comparing adjacent elements and swapping them if they are in the wrong order. The only real difference is that it does it in both directions instead of only going from left to right.

Because of this, cocktail sort manages to get around the “turtles problem” (small elements near the end of the list slowing down the algorithm) of bubble sort, however it still retains the same worst case computational complexity.

An other way of thinking at this sorting algorithm is:

Each time I shake the cocktail: the heavier value goes down when I shake down and the lighter value goes up when I shake up.

Homonyms

  • Bidirectional Bubble sort
  • Martini sort
  • Ripple sort
  • Shaker sort
  • Shufle sort
  • Shuttle sort

Steps

  • While there is swap needed:
    • 1. Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
    • 2. If no swap made, then stop: we are done (optimization).
    • 3. Remove the current last element from possible comparison (optimization).
    • 1.bis. Compare each pair of adjacent elements from the end of an array and, if they are in reversed order, swap them.
    • 2.bis. If no swap made, then stop: we are done (optimization).
    • 3.bis. Remove the current first element from possible comparison (optimization).

Pseudo-Code

void CocktailSort (Iterator begin, Iterator end)
{
  if (distance(begin, end) < 2)
    return;

  int beginIdx = 0;
  int endIdx = distance - 1;
  bool hasSwapped = true;
  while (hasSwapped && beginIdx < distance - 1)
  {
    hasSwapped = false;

    // for each element from beginning - bubble it up until the end.
    for (auto it = begin + beginIdx; it < begin + endIdx; ++it)
      if (Compare(it, it + 1))
      {
        Swap(it, it + 1);
        hasSwapped = true;
      }
    --endIdx;

    if (!hasSwapped)
      break;

    // for each element from the end- bubble it down until the beginning.
    for (auto it = begin + endIdx - 1; it >= begin + beginIdx; --it)
      if (Compare(it, it + 1))
      {
        Swap(it, it + 1);
        hasSwapped = true;
      }

    ++beginIdx;
  }
}

Time

Best

The best configuration occurs when all elements are already sorted or nealy sorted.
Consequently, we have to go through the first sequence only once: O(n).

Average / Worst

Just like Bubble sort, the worst case O(n2) occurs when the sequence is in reverse order. First, the highest value is bubbled down until the end, and the lowest value is bubbled up to the beggining; then the loop start again starting at (begin + 1) to (end - 1) and so forth.

Space

Cocktail Sort does not use any buffer nor does make any recursion. Thus, it requires O(1) space in all case.