## Introduction

This post will explore how to implement Cocktail Sort in C++. Cocktail Sort, or Bidirectional Bubble Sort, is a variation of Bubble Sort that improves performance by sorting elements in both directions on each pass through the array. We will cover key points, pseudocode, time complexity, and a step-by-step walkthrough of the C++ implementation. We’ll also provide performance comparisons with other sorting algorithms.

## What is Cocktail Sort?

Cocktail Sort is a simple comparison-based sorting algorithm that works similarly to Bubble Sort but with an enhancement. In Cocktail Sort, the sorting process proceeds in two directions. Instead of only making a forward pass through the array, Cocktail Sort makes both a forward and backward pass during each iteration. In the forward pass, it pushes larger elements towards the end of the array by swapping adjacent elements if they are in the wrong order. Then, in the backward pass, smaller elements are pushed towards the beginning of the array in the same way.

This bidirectional approach helps in cases where the array is partially sorted or nearly sorted, as it can eliminate unnecessary passes through the already sorted parts of the array. However, despite this improvement, Cocktail Sort shares the same time complexity as Bubble Sort and is inefficient for large datasets. Its best-case time complexity is O(n), which occurs when the array is sorted. Cocktail Sort runs with an O(n²) time complexity in average and worst cases. It is an in-place and stable sorting algorithm, meaning it does not require additional memory for sorting and preserves the relative order of equal elements.

Below, you can see a visualization of how Cocktail Sort works. Choose the length of your array in the box next to `Array Size (Max 30)`

then click `Generate Random Array`

to generate the numbers, then click `Start Sorting`

.

## Pseudocode for Cocktail Sort

Below is the pseudocode for Cocktail Sort, which includes forward and backwards passes through the array to sort it in both directions.

function CocktailSort(arr): n = length(arr) start = 0 end = n - 1 swapped = true while swapped is true: swapped = false # Left to right pass for i from start to end - 1: if arr[i] > arr[i + 1]: swap arr[i] and arr[i + 1] swapped = true if swapped is false: break swapped = false end = end - 1 # Right to left pass for i from end - 1 to start: if arr[i] > arr[i + 1]: swap arr[i] and arr[i + 1] swapped = true start = start + 1

### Time Complexity

**Best Case**: O(n) – When the array is sorted.**Average Case**: O(n²) – Due to the nested loops.**Worst Case**: O(n²) – When the array is sorted in reverse order.**Space Complexity**: O(1) – Only a few extra variables are used, making it an in-place sorting algorithm.

## C++ Implementation of Cocktail Sort

Here’s the implementation of Cocktail Sort in C++:

#include <iostream> using namespace std; void cocktailSort(int arr[], 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 (arr[i] > arr[i + 1]) { swap(arr[i], arr[i + 1]); swapped = true; } } // If no elements were swapped, the array is sorted if (!swapped) break; // Reset swapped for backward pass swapped = false; // Move the end point one step back --end; // Backward pass for (int i = end - 1; i >= start; --i) { if (arr[i] > arr[i + 1]) { swap(arr[i], arr[i + 1]); swapped = true; } } // Move the start point one step forward ++start; } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } int main() { int arr[] = {5, 1, 4, 2, 8, 0, 2}; int n = sizeof(arr) / sizeof(arr[0]); // Print initial array cout << "Initial array: \n"; printArray(arr, n); // Sort the array cocktailSort(arr, n); // Print sorted array cout << "Sorted array: \n"; printArray(arr, n); return 0; }

**Output:**

Initial array: 5 1 4 2 8 0 2 Sorted array: 0 1 2 2 4 5 8

## Step-by-Step Explanation with an Example Array

Let’s walk through an example using the array `{5, 1, 4, 2, 8, 0, 2}`

.

**Forward Pass (Left to Right)**:- Compare
`5`

and`1`

, swap them. Array becomes`{1, 5, 4, 2, 8, 0, 2}`

. - Compare
`5`

and`4`

, swap them. Array becomes`{1, 4, 5, 2, 8, 0, 2}`

. - Compare
`5`

and`2`

, swap them. Array becomes`{1, 4, 2, 5, 8, 0, 2}`

. - No swap is needed for
`5`

and`8`

. Compare`8`

and`0`

, swap them. Array becomes`{1, 4, 2, 5, 0, 8, 2}`

. - Compare
`8`

and`2`

, swap them. Array becomes`{1, 4, 2, 5, 0, 2, 8}`

.

- Compare
**Backward Pass (Right to Left)**:- Compare
`0`

and`2`

, no swap needed. Compare`0`

and`5`

, swap them. Array becomes`{1, 4, 2, 0, 5, 2, 8}`

. - Compare
`4`

and`0`

, swap them. Array becomes`{1, 2, 4, 0, 5, 2, 8}`

. - Compare
`2`

and`1`

, no swap needed.

- Compare

The algorithm continues until no swaps are made.

## Performance Test Comparing Bubble Sort to Cocktail Sort

In this section, we evaluate the performance of **Cocktail Sort** and **Bubble Sort** across different array types (reverse sorted, sorted, and random) and array sizes (100, 10,000, and 100,000). The goal is to highlight how each algorithm behaves under varying conditions and to identify which algorithm performs better as the data size increases. Below are the results and key takeaways from the tests.

#include <iostream> #include <chrono> #include <algorithm> // for std::random_shuffle #include <cstdlib> // for rand(), srand() #include <ctime> // for seeding rand() using namespace std; using namespace std::chrono; // Cocktail Sort void cocktailSort(int arr[], 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 (arr[i] > arr[i + 1]) { swap(arr[i], arr[i + 1]); swapped = true; } } if (!swapped) break; swapped = false; --end; // Backward pass for (int i = end - 1; i >= start; --i) { if (arr[i] > arr[i + 1]) { swap(arr[i], arr[i + 1]); swapped = true; } } ++start; } } // Bubble Sort void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { for (int j = 0; j < n - i - 1; ++j) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } } } // Function to print execution time void printExecutionTime(const string& sortName, const string& arrayType, int size, microseconds duration) { cout << sortName << " (" << arrayType << ", size " << size << "): " << duration.count() << " µs" << endl; } // Helper functions to create different arrays void generateReverseSortedArray(int arr[], int size) { for (int i = 0; i < size; ++i) { arr[i] = size - i; } } void generateSortedArray(int arr[], int size) { for (int i = 0; i < size; ++i) { arr[i] = i + 1; } } void generateRandomArray(int arr[], int size) { srand(time(0)); // Seed the random number generator for (int i = 0; i < size; ++i) { arr[i] = rand() % size; } } void testPerformance(int size) { int* arr = new int[size]; int* tempArr = new int[size]; // Test on reverse sorted array generateReverseSortedArray(arr, size); copy(arr, arr + size, tempArr); auto start = high_resolution_clock::now(); cocktailSort(tempArr, size); auto end = high_resolution_clock::now(); printExecutionTime("Cocktail Sort", "Reverse Sorted", size, duration_cast<microseconds>(end - start)); copy(arr, arr + size, tempArr); start = high_resolution_clock::now(); bubbleSort(tempArr, size); end = high_resolution_clock::now(); printExecutionTime("Bubble Sort", "Reverse Sorted", size, duration_cast<microseconds>(end - start)); // Test on sorted array generateSortedArray(arr, size); copy(arr, arr + size, tempArr); start = high_resolution_clock::now(); cocktailSort(tempArr, size); end = high_resolution_clock::now(); printExecutionTime("Cocktail Sort", "Sorted", size, duration_cast<microseconds>(end - start)); copy(arr, arr + size, tempArr); start = high_resolution_clock::now(); bubbleSort(tempArr, size); end = high_resolution_clock::now(); printExecutionTime("Bubble Sort", "Sorted", size, duration_cast<microseconds>(end - start)); // Test on random array generateRandomArray(arr, size); copy(arr, arr + size, tempArr); start = high_resolution_clock::now(); cocktailSort(tempArr, size); end = high_resolution_clock::now(); printExecutionTime("Cocktail Sort", "Random", size, duration_cast<microseconds>(end - start)); copy(arr, arr + size, tempArr); start = high_resolution_clock::now(); bubbleSort(tempArr, size); end = high_resolution_clock::now(); printExecutionTime("Bubble Sort", "Random", size, duration_cast<microseconds>(end - start)); delete[] arr; delete[] tempArr; } int main() { // Test with different sizes testPerformance(100); testPerformance(10000); testPerformance(100000); return 0; }

### Performance Test Results: Cocktail Sort vs Bubble Sort C++

Array Type | Size | Cocktail Sort Time (µs) | Bubble Sort Time (µs) |
---|---|---|---|

Reverse Sorted | 100 | 22 | 22 |

Sorted | 100 | 0 | 9 |

Random | 100 | 20 | 22 |

Reverse Sorted | 10000 | 227564 | 271297 |

Sorted | 10000 | 18 | 89319 |

Random | 10000 | 209188 | 262431 |

Reverse Sorted | 100000 | 23633330 | 23329300 |

Sorted | 100000 | 186 | 9087459 |

Random | 100000 | 21632131 | 28883082 |

**Note on 0 Microsecond Values**:

For some sorted arrays, you may notice **0 microseconds** as the time recorded for Cocktail Sort. This occurs because the algorithm detects the sorted state in its first pass and terminates almost immediately, especially for smaller arrays. The negligible time it takes to confirm that no swaps are needed can result in a recorded time of 0 due to the precision limits of the measurement.

#### Key Takeaways

- Small Arrays (100 elements): Nearly identical performance across all array types.
- Large Arrays (10,000+ elements):
- Cocktail Sort outperforms Bubble Sort, especially for random and reverse-sorted arrays.
- At 100,000 elements: Cocktail Sort ~21.6s, Bubble Sort ~28.8s for random arrays.

- Sorted Arrays: Both algorithms excel, with Cocktail Sort finishing almost instantly.
- Reverse Sorted Arrays: Most challenging for both, but Cocktail Sort shows a slight advantage.

- Overall:
- Cocktail Sort is consistently better for larger, more complex datasets.
- Both are unsuitable for very large datasets compared to advanced algorithms.
- Cocktail Sort offers a modest improvement over Bubble Sort in real-world scenarios.

## Advantages of Cocktail Sort

Cocktail Sort performs better on nearly sorted data due to its bidirectional approach, which reduces passes over the array. It efficiently handles “turtle” values (small values near the end) and can terminate earlier when the array becomes sorted. Generally, it slightly improves over Bubble Sort, especially for larger datasets and reverse-sorted arrays.

## Limitations of Cocktail Sort

Despite its advantages, Cocktail Sort’s time complexity remains O(n²), making it inefficient for large arrays as performance degrades quickly with increasing input size. Its practical use is limited, being outperformed by more advanced algorithms like Quick Sort and Merge Sort. While it uses in-place sorting, it requires extra variables for swapping. Cocktail Sort lacks adaptability, does not adjust well to different data distributions, and its performance heavily depends on the initial order of elements. As a result, it’s mainly used for educational purposes or very small datasets.

## Conclusion

**Cocktail Sort**, a modest improvement over Bubble Sort, demonstrates how small algorithmic tweaks can enhance performance. While unsuitable for large-scale applications, it is an educational tool that bridges the gap between basic and advanced sorting techniques. Its bidirectional approach introduces optimization concepts, making it valuable for teaching algorithm analysis and improvement strategies. Cocktail Sort may find practical use in niche scenarios with strict memory constraints or small datasets. Ultimately, it represents a stepping stone in algorithmic thinking, encouraging students and developers to explore more efficient sorting methods while understanding the trade-offs between simplicity and performance in algorithm design.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Cocktail Sort in:

JavaScript – How To Do Cocktail Sort in JavaScript

Python – How To Do Cocktail Sort in Python

Rust – How to do Cocktail Sort in Rust

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.