How To Do Cocktail Sort in JavaScript

Introduction

Cocktail Sort, also known as Bidirectional Bubble Sort or Shaker Sort, is a variation of Bubble Sort that sorts the array in both directions on each pass through the list. By alternating the sorting direction, Cocktail Sort eliminates turtles (small elements stuck at the end) more quickly, improving the efficiency of Bubble Sort in certain cases.

In this post, we will go over how to implement Cocktail Sort in JavaScript, walk through an example, and discuss the pros, cons, and performance considerations of using this algorithm.

What is Cocktail Sort?

Cocktail Sort is an extension of Bubble Sort that goes through the array from both forward and backwards directions in each pass. This helps reduce the number of comparisons for cases where large elements are at the start, and small elements are at the end of the array.

• Forward pass: Like Bubble Sort, it compares adjacent elements and moves the larger one to the end.
• Backward pass: It then compares elements from the back of the array to the start, moving smaller elements to the front.

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

Here’s the pseudocode for Cocktail Sort:

procedure cocktailSort(A : array of items)
    repeat
        swapped = false
        
        // Forward pass (left to right)
        for i = 0 to n-2 do
            if A[i] > A[i+1] then
                swap(A[i], A[i+1])
                swapped = true

        // If no elements were swapped, the array is sorted
        if not swapped then
            break
        
        swapped = false
        
        // Backward pass (right to left)
        for i = n-2 downto 0 do
            if A[i] > A[i+1] then
                swap(A[i], A[i+1])
                swapped = true
                
    until swapped = false

Time and Space Complexities

• Time Complexity:
  • Worst-case: O(n²) — similar to Bubble Sort, as each element might be compared.
  • Best-case: O(n) — if the array is already sorted.
• Space Complexity:
  • O(1) — Cocktail Sort operates in place and doesn’t require extra memory.

JavaScript Implementation

Now, let’s implement Cocktail Sort in JavaScript:

function cocktailSort(arr) {
    let swapped = true;
    let start = 0;
    let end = arr.length;

    while (swapped) {
        swapped = false;

        // Forward pass
        for (let i = start; i < end - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]; // Swap elements
                swapped = true;
            }
        }

        // If no elements were swapped, the array is sorted
        if (!swapped) {
            break;
        }

        // Otherwise, reset the swapped flag for the backward pass
        swapped = false;

        // Decrement the end point, as the last element is already sorted
        end--;

        // Backward pass
        for (let i = end - 1; i > start; i--) {
            if (arr[i - 1] > arr[i]) {
                [arr[i - 1], arr[i]] = [arr[i], arr[i - 1]]; // Swap elements
                swapped = true;
            }
        }

        // Increment the starting point, as the first element is already sorted
        start++;
    }

    return arr;
}

// Example usage:
const array = [5, 3, 8, 4, 2, 6, 1, 9];
console.log("Original Array:", array);
console.log("Sorted Array:", cocktailSort(array));

Output:

Original Array: [
  5, 3, 8, 4,
  2, 6, 1, 9
]
Sorted Array: [
  1, 2, 3, 4,
  5, 6, 8, 9
]

Step-by-Step Explanation of Cocktail Sort

Let’s break down how Cocktail Sort works for the array [5, 3, 8, 4, 2, 6, 1, 9]:

1. Initial Array:
   • [5, 3, 8, 4, 2, 6, 1, 9]
2. First Forward Pass (Left to Right):
   • Compare 5 and 3 → Swap → [3, 5, 8, 4, 2, 6, 1, 9]
   • Compare 5 and 8 → No swap
   • Compare 8 and 4 → Swap → [3, 5, 4, 8, 2, 6, 1, 9]
   • Compare 8 and 2 → Swap → [3, 5, 4, 2, 8, 6, 1, 9]
   • Compare 8 and 6 → Swap → [3, 5, 4, 2, 6, 8, 1, 9]
   • Compare 8 and 1 → Swap → [3, 5, 4, 2, 6, 1, 8, 9]
   • Compare 8 and 9 → No swap
   • End of first forward pass: [3, 5, 4, 2, 6, 1, 8, 9]
3. First Backward Pass (Right to Left):
   • Compare 8 and 9 → No swap
   • Compare 1 and 6 → Swap → [3, 5, 4, 2, 1, 6, 8, 9]
   • Compare 1 and 2 → Swap → [3, 5, 4, 1, 2, 6, 8, 9]
   • Compare 1 and 4 → Swap → [3, 5, 1, 4, 2, 6, 8, 9]
   • Compare 1 and 5 → Swap → [3, 1, 5, 4, 2, 6, 8, 9]
   • Compare 1 and 3 → Swap → [1, 3, 5, 4, 2, 6, 8, 9]
   • End of first backward pass: [1, 3, 5, 4, 2, 6, 8, 9]
4. Second Forward Pass:
   • Compare 3 and 5 → No swap
   • Compare 5 and 4 → Swap → [1, 3, 4, 5, 2, 6, 8, 9]
   • Compare 5 and 2 → Swap → [1, 3, 4, 2, 5, 6, 8, 9]
   • Compare 5 and 6 → No swap
   • End of second forward pass: [1, 3, 4, 2, 5, 6, 8, 9]
5. Second Backward Pass:
   • Compare 5 and 6 → No swap
   • Compare 2 and 4 → Swap → [1, 3, 2, 4, 5, 6, 8, 9]
   • Compare 2 and 3 → Swap → [1, 2, 3, 4, 5, 6, 8, 9]
   • End of second backward pass: [1, 2, 3, 4, 5, 6, 8, 9]
6. Third Forward Pass:
   • Compare 1 and 2 → No swap
   • Compare 2 and 3 → No swap
   • Compare 3 and 4 → No swap
   • End of third forward pass: [1, 2, 3, 4, 5, 6, 8, 9]
7. Third Backward Pass:
   • Compare 3 and 4 → No swap
   • Compare 2 and 3 → No swap
   • Compare 1 and 2 → No swap
   • End of third backward pass: [1, 2, 3, 4, 5, 6, 8, 9]

The array is fully sorted, so the algorithm terminates.

Summary of Swaps:

• First Forward Pass: 5 with 3, 8 with 4, 8 with 2, 8 with 6, 8 with 1.
• First Backward Pass: 6 with 1, 2 with 1, 4 with 1, 5 with 1, 3 with 1.
• Second Forward Pass: 5 with 4, 5 with 2.
• Second Backward Pass: 4 with 2, 3 with 2.

This detailed breakdown helps clarify how Cocktail Sort compares and swaps elements in both directions, ensuring that the array is sorted more efficiently than traditional Bubble Sort. To see how Cocktail Sort performs, visit our Sorting Algorithm Visualizer.

Pros and Cons of Cocktail Sort

Pros:

• Efficient for small datasets: Cocktail Sort works well for small arrays, similar to Bubble Sort but slightly optimized.
• Eliminates turtles faster: The bidirectional nature helps eliminate small values at the end of the array quicker.
• Simple to implement: The algorithm is easy to understand and implement.

Cons:

• Inefficient for large datasets: Like Bubble Sort, Cocktail Sort is a quadratic time algorithm, making it unsuitable for large datasets.
• Not widely used in practice: Due to its O(n²) time complexity, more advanced algorithms like Quick Sort or Merge Sort are preferred for large datasets.

When to Use Cocktail Sort

Cocktail Sort is best used when:

• You’re working with small datasets that don’t require a highly efficient sorting algorithm.
• You need a simple sorting algorithm that’s easy to understand and implement.
• You want a slight improvement over Bubble Sort, especially when dealing with arrays with small and large elements scattered throughout.

Conclusion

Cocktail Sort improves the basic Bubble Sort by sorting in both directions during each pass. While it’s easy to implement and great for small datasets, its quadratic time complexity makes it unsuitable for large data sets. However, understanding Cocktail Sort helps build a solid foundation for more complex sorting algorithms like Quick Sort or Merge Sort.

Congratulations on reading to the end of the tutorial!

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

In Python – How to do Cocktail Sort in Python

In Rust – How to do Cocktail Sort in Rust

Have fun and happy researching!