Bubble sort works like arranging cards by swapping neighbouring ones repeatedly. Larger values rise into place quickly, but smaller values near the end move forward slowly, one step at a time, making the method inefficient for larger datasets in DSA. The cocktail sort algorithm was designed specifically to solve this issue. Often referred to as Shaker Sort or Bidirectional Bubble Sort, it tweaks the classic approach by traversing the array in both directions. This guide will break down how the cocktail sort works, provide a cocktail sort example, and look at how to implement cocktail sort in C++ and other languages.
Also Read – Advance Data Structure and Algorithms
What is Cocktail Sort?
At its heart, cocktail sort is an extension of bubble sort. In a standard bubble sort, the algorithm always passes through the list from left to right. It finds the largest element and pushes it to the end.
The cocktail sort algorithm changes this process by adding a second pass. Once it reaches the end of the list and places the largest element, it immediately turns around. It then moves from right to left, carrying the smallest element back to the beginning. This back-and-forth motion is why it is called the “cocktail” or “shaker” sort, it resembles the movement of a cocktail shaker.
Why Do We Need It?
In sorting terminology, we talk about “rabbits” and “turtles.” Rabbits are large elements at the beginning of a list that move quickly to the end. Small items at the bottom of a list that slowly advance to the top are called turtles. While bubble sort handles rabbits well, it struggles with turtles. It solves this by catching those turtles on the backward pass and moving them to their correct spot much faster.
How Does the Cocktail Sort Algorithm Work?
Understanding the logic behind this algorithm is easier when you break it down into a step-by-step process. Here is the general flow:
- Forward Pass: Start from the beginning of the array. Compare each pair of adjacent elements. If the left element is greater than the right, swap them. By the end of this pass, the largest element is at the end.
- Update Boundaries: Since the last element is now in its correct place, we reduce the “end” boundary of our search area.
- Backward Pass: Start from the element just before the newly placed largest one. Move toward the beginning of the array, comparing adjacent pairs. If the right element is smaller than the left, swap them. By the end of this pass, the smallest element is at the very start.
- Update Boundaries Again: Since the first element is now in its correct place, we increase the “start” boundary.
- Repeat: Continue these two passes until no more swaps occur, meaning the list is fully sorted.
A Cocktail Sort Example
Let’s look at an example using a simple unsorted list: [5, 1, 4, 2, 8].
First Forward Pass:
- Compare 5 and 1: Swap (1, 5, 4, 2, 8)
- Compare 5 and 4: Swap (1, 4, 5, 2, 8)
- Compare 5 and 2: Swap (1, 4, 2, 5, 8)
- Compare 5 and 8: No swap.
- End result: 8 is at the correct position.
First Backward Pass:
- Compare 5 and 2: Swap (1, 4, 2, 5, 8)
- Compare 2 and 4: Swap (1, 2, 4, 5, 8)
- Compare 2 and 1: No swap.
- End result: 1 is at the correct position.
In this specific example, the list became sorted faster than a traditional bubble sort because the backward pass immediately addressed the smaller numbers.
Also Read – Introduction to Red-Black Tree
Cocktail Sort in C++
For students diving into DSA, seeing the code is essential. Below is a clean implementation of CocktailSort in C++.
#include <iostream>
#include <vector>
void cocktailSort(int a[], int n) {
bool swapped = true;
int start = 0;
int end = n – 1;
while (swapped) {
swapped = false;
// Forward pass
for (int i = start; i < end; ++i) {
if (a[i] > a[i + 1]) {
std::swap(a[i], a[i + 1]);
swapped = true;
}
}
if (!swapped) break;
swapped = false;
–end;
// Backward pass
for (int i = end – 1; i >= start; –i) {
if (a[i] > a[i + 1]) {
std::swap(a[i], a[i + 1]);
swapped = true;
}
}
++start;
}
}
This code snippet for cocktail sort in C++ uses a boolean flag, ‘swapped’. If no swaps happen during a full pass, the algorithm knows the array is sorted and exits early, which saves processing time.
Complexity Analysis in Cocktail Sort
When choosing an algorithm, you must consider efficiency. It shares similar complexity traits with bubble sort but performs better in specific “turtle” scenarios.
- Worst Case Time Complexity: O(n²) : This scenario happens when the array is sorted in reverse order.
- Average Case Time Complexity: O(n²) : On average, it still requires nested-style comparisons.
- Best Case Time Complexity: O(n) : This occurs if the array is already sorted.
- Space Complexity: O(1) — It is an “in-place” algorithm, meaning it doesn’t require extra memory to store copies of the list.
Cocktail Sort Visualization
If you look at a cocktail sort visualization, you will notice a distinct “shaking” motion.
- The window of unsorted elements shrinks from both sides.
- The “active” zone moves like a wave back and forth.
- Unlike Bubble Sort, where the sorted portion only grows from the right, here it grows from both the left and the right simultaneously.
This cocktail sort visualization helps programmers understand why the algorithm is more balanced. While it doesn’t change the O(n²) mathematical limit, the constant factor is often smaller in practice for many datasets.
Also Read – Geometric Algorithms
When Should I Use CocktailSort?
While advanced algorithms like QuickSort or MergeSort are faster for large datasets, cocktailsort has its niche. It is useful when:
- The list is mostly sorted but has a few small elements near the end.
- You are working in a memory-constrained environment where O(1) space is mandatory.
- You are teaching or learning the fundamentals of sorting logic and bidirectional traversal.
FAQs
Is cocktailsort faster than bubble sort?
In most practical cases, yes. While they have the same O(n²) worst-case complexity, the cocktailsort algorithm performs better because it moves small elements to the front much faster than bubble sort does.
What is the main advantage of the cocktailsort algorithm?
The main advantage is its ability to handle "turtles", small values located at the end of a list, more effectively when using a bidirectional pass.
Can I implement cocktailsorting in C++ for large data?
You can, but it is not recommended. For large datasets, O(n²) algorithms are too slow. You should look into MergeSort or QuickSort for better performance.