Traces by Cocktail Sort on random sequences {50}

Swaps by Cocktail Sort on random sequences {50}

Traces by Cocktail Sort on reversed sequence {50} (worst case)

Swaps by Cocktail Sort on reversed sequence {50} (worst case)

Cocktail sort, just like the 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.

Another way of thinking of this sorting algorithm is:

Each time I shake the cocktail: the more massive 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
• Shuffle 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 the 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 the possible comparison (optimization).

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;
  }
}

Displace the highest value at the end by swapping it successively (Left To Right).

Displace the lowest value at the beginning by swapping it successively (Right To Left).
As it can be seen, highest and lowest value are now excluded from the processing range.

Further illustration of the previous descriptions.

Algorithm ends when we fully square-iterated the sequence: sort is done.

Time

Best

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

Average / Worst

Just like the Bubble sort, the worst case O(n²) 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 beginning; then the loop starts 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.