How to implement cocktail sort in Python

Cocktail sort is a modification of bubble sort. It is also known as bidirectional bubble sort, cocktail shaker sort, shaker sort, shuffle sort, shuttle sort, happy hour sort, or ripple sort. It works in sorting elements in both directions. The process of sorting starts by shifting the largest element to the rightmost side (like bubble sort). After that, the algorithm moves in the opposite direction and shifts the smallest element to the leftmost side. The smallest and largest elements are placed at their final positions in the first iteration. These steps are continued on the unsorted array until the entire array is sorted.

Play the following slides to visualize the working of the cocktail sort:

Note: The cocktail sort algorithm, similar to other variants of bubble sort, is used as an educational tool. More efficient sorting algorithms, i.e., merge sort, quick sort, or timsort, are preferred in real-world applications. Most programming languages use these algorithms for their built-in sorting algorithms. For example, Python uses timsort in its built-in sorted() function and .sort() method.

Algorithm

Let’s discuss the sequence of the steps for the algorithm:

How is cocktail sort different from bubble sort?

The cocktail sort is a bit different from the bubble sort. Let’s discuss them below:

• The bubble sort algorithm passes through the array from left to right, but the cocktail sort passes in both directions.
• The number of comparisons in cocktail sort is less than in bubble sort because, in each iteration, it excludes the sorted array and performs sorting on the remaining unsorted array. However, this has a minor impact on the performance, and the overall complexity remains the same.

When to use cocktail sort instead of bubble sort?

The cocktail sort should be used instead of bubble sort in the following scenarios:

• The cocktail sort performs better in sorting small data than the bubble sort.
• The cocktail sort should be utilized on partially sorted data because it performs better than bubble sort in this scenario.

Implementation code

Let’s implement the code of cocktail sort in the following playground:

Code explanation

Let’s discuss the above code:

• Lines 2–3: We define some variables swapped, start, and end to store of the indices.
• Lines 5–21: We use the while loop to implement the sorting in which:
  • Lines 6–11: We set the swapped flag to False and used the for loop for the forward pass. In the forward pass, we do element-wise swapping if required and set the swapped flag to True. At the end of the for loop, the end index is shifted to the previous index.
  • Line 13: We break the while loop if no swapping occurs in the forward pass.
  • Lines 15–20: We set the swapped flag to False and used the for loop for the backward pass. In the backward pass, we do element-wise swapping if required and set the swapped flag to True. At the end of the for loop, the start index is shifted to the next index.
• Lines 24–26: We create an unsorted array and call the cocktail_sort() function. We use print statements to show the array before and after sorting.

Complexity

The worst-case and average-case time complexity of the cocktail shaker algorithm is O(n2)O(n^2).

However, when the list is almost sorted before using the sorting algorithm, its complexity approaches O(n)O(n). For example, if each element is at most kk positions away from its final position, the complexity of the cocktail sort will be O(kn)O(kn).

In the array, [9,2,3,4,5,6,7,8,1][9,2,3,4,5,6,7,8,1], there are two elements away from their final positions. It required only one iteration of cocktail sort for shifting 99 and 11 to their actual positions.

The space complexity of the cocktail shaker is O(1)O(1).

Pros and cons

Let’s discuss some pros and cons of the cocktail sort.

Pros

• The cocktail sort algorithm is simple to understand and implement. It is a good choice for sorting small datasets.
• It performs better than bubble sort, where the array is nearly sorted or a few elements are misplaced.
• It is a stable sorting algorithm, which means it maintains the order of similar elements in the sorted array.
• It is an in-place sorting algorithm, which means it doesn’t require any extra space to sort the data.

Cons

• Cocktail sort can be slow for large datasets, as its worst-case time complexity is O(n2)O(n^2).
• It requires keeping track of starting and ending indices.