How To Do Cocktail Sort in C++

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

1. 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}.
2. 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.

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