Cocktail Sort Visualization

What is Cocktail Sort?

Cocktail sort, also known as bidirectional bubble sort, cocktail sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuffle sort, or shuttle sort, is an extension of bubble sort.

The Bubble sort algorithm always traverses elements from left and moves the largest element to its correct position in first iteration and second largest in the second iteration, and so on. Cocktail Sort traverses through a given array in both directions alternatively.

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 the bubble sort. However, it still retains the same worst-case computational complexity. 

Sorting algorithms are used in many different contexts, including computer science, mathematics, and business. They're also useful for organizing data into groups. The operation is such that a sorting algorithm traverses through an ordered list by comparing each element to its neighbors until they are sorted.

Cocktail Sort

The Cocktail Sort algorithm is a modernized version of the Bubble Sort. The traditional bubble sort always starts with the largest element and moves it to its correct position in the first iteration, then does this again for the second-largest size until all elements are sorted...you get where I'm going with this? By switching things up at every other iteration, cocktail sorts break down barriers that limit bubble sorts from being efficient enough on large arrays by not allowing them to go through unnecessary iterations on one specific region (or cluster) before moving onto another section of an array.

How does Cocktail Sort algorithm work?

There are two stages to every iteration of the algorithm:

1. The array is looped from left to right in the first stage, just like the Bubble Sort. When the left and right items are compared, the left value is greater than the right value, and that value is swapped. After the first iteration, the number with the largest value will be at the end of the array.
2. After the second stage, the array is looped through in reverse - starting from the item immediately following the most recently sorted item and returning to the start. A similar comparison is conducted here, and if necessary, adjacent items are swapped.
3. The loop stops when a pass does no swap.

After the first forward pass, the greatest element of the array will be present at the end last index of the array. After the first backward pass, the smallest element of the array will be present at the first index of the array.

Cocktail performs better than Bubble Sort despite having the same time complexity. Cocktail sorting is typically faster than bubble sorting by less than two times. During cocktail shaker sorting, as bidirectional swaps are made, the range of possible swaps will reduce per pass, thereby reducing run time slightly.

Use the interactive tool to see the algorithm in action.