Implementation of the cocktail sort in C++

Cocktail sort is a modification of bubble sort. It has many other names, such as bidirectional bubble sort, shuffle sort, shuttle sort, cocktail shaker sort, shaker sort, happy hour sort, or ripple sort. It works to sort elements in both directions. The process of sorting starts by shifting the largest element to the rightmost position (like bubble sort). After that, the algorithm moves in the opposite direction and shifts the smallest element to the leftmost position. 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:

canvasAnimation-image
1 of 45

Note: Similar to the other variants of bubble sort, the cocktail sort is mostly used as an educational tool. In real-world applications, an efficient sorting algorithm, i.e., merge sort, quicksort, or Timsort, is preferred. 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:

swapped := True
start := 0
end := size of array - 1
while swapped is True
    swapped := False
    for i from start to end
        if array[i] > array[i+1]
            swap both values
            swapped := True
    end := end-1
    if swapped is False
        break the loop
    swapped := False
    for i from end to start
        if array[i] < array[i-1]
            swap both values
            swapped := True
    start := start+1
return array
Pseudocode of the cocktail sort algorithm

How is cocktail sort different from bubble sort?

The working of the cocktail sort is similar to the bubble sort, but there are some differences. Let’s discuss them below:

  • The bubble sort algorithm iterates from the start to the end of the array, 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:

#include <iostream>
#include <vector>
std::vector<int> cocktail_sort(std::vector<int>& arr) {
    bool swapped = true;
    int start = -1;
    int end = arr.size() - 1;
    while(swapped) {
        swapped = false; // Reset the flag for forward pass
        for (int i = ++start; i < end; i++) {
            if (arr[i] > arr[i+1]) { // Compare and shift the larger element to the right
                std::swap(arr[i], arr[i+1]);
                swapped = true;
            }
        }
        if (!swapped) break; // Break the loop if no swapping happens
        swapped = false; // Reset the flag for backward pass
        for (int i = --end; i > start; i--) {
            if (arr[i] < arr[i - 1]) { // Compare and shift the smaller element to the left
                std::swap(arr[i], arr[i - 1]);
                swapped = true;
            }
        }
    }
    return arr;
}
int main() {
    std::vector<int> unsorted_arr = {15, 13, 24, 7, 18, 3, 22, 9};
    std::cout << "Unsorted array: ";
    for (int num : unsorted_arr) {
        std::cout << num << " ";
    }
    std::vector<int> sorted_arr = cocktail_sort(unsorted_arr);
    std::cout << "\nSorted array: ";
    for (int num : sorted_arr) {
        std::cout << num << " ";
    }
    return 0;
}

Code explanation

Let’s discuss the code below:

  • Lines 5–7: We define some variables to keep tracking the swapping, start, and end indices during the sorting.
  • Lines 9–27: We use the while loop to implement the sorting in which:
    • Lines 10–16: We set the swapped flag to false and used the for loop for the forward pass. We initialize the loop with an increment to the start value using ++start. In the forward pass, we do element-wise swapping if required, and set the swapped flag to true.
    • Line 18: We break the while loop if no swapping occurs in the forward pass.
    • Lines 20–26: We set the swapped flag to false and use the for loop for the backward pass. We initialize the loop with a decrement to the end value using --end. In the backward pass, we do element-wise swapping if required, and set the swapped flag to true.
  • Lines 32–36: We create an unsorted array and print the array before sorting.
  • Lines 38–42: We call the cocktail_sort() function and print the array after sorting.

Complexity

The worst 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 requires 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

  1. The cocktail sort algorithm is easy to understand and use. It can be a good pick for sorting small datasets.
  2. It performs better than bubble sort where the array is nearly sorted, or a few elements are misplaced.
  3. It’s a stable sorting algorithm, which means it maintains the order of similar elements in the sorted array.
  4. It’s an in-place sorting algorithm, which means it doesn’t require any extra space to sort the data.

Cons

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

Unlock your potential: Sorting algorithms series – all in one place!

To continue your exploration of sorting algorithms, check out our series of Answers below:

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved