How To Do Cocktail Sort in Python

Cocktail Sort is a bidirectional variation of Bubble Sort, where elements are alternately sorted from left to right and right to left. This alternating approach allows smaller elements to move to the front and larger elements to the end in fewer passes than the traditional Bubble Sort. While Cocktail Sort is simple to implement, its time complexity remains O(n²) in both average and worst cases, which makes it inefficient for large datasets. This blog post will walk through implementing Cocktail Sort in Python, provide detailed pseudocode, and evaluate its performance on different arrays.

What is Cocktail Sort?

Cocktail Sort, Shaker Sort or Bidirectional Bubble Sort is a simple comparison-based sorting algorithm. It alternates between left-to-right and right-to-left passes through the array, moving larger elements to the end and smaller elements to the beginning. This bidirectional approach reduces the number of passes compared to traditional Bubble Sort, making it more efficient for arrays that are already partially sorted.

Time Complexity:

• Best Case: O(n) when the array is already sorted.
• Average Case: O(n²), similar to Bubble Sort.
• Worst Case: O(n²) when the array is in reverse order.

---

How Cocktail Sort Works

The Cocktail Sort algorithm works as follows:

1. Left-to-Right Pass: Traverse the array from left to right, swapping adjacent elements if they are in the wrong order (i.e., larger element before a smaller one).
2. Right-to-Left Pass: After the first pass, traverse the array in the opposite direction, from right to left, again swapping adjacent elements if needed.
3. Repeat: Continue alternating between the left-to-right and right-to-left passes until no swaps are required, indicating that the array is sorted.

---

Pseudocode for Cocktail Sort

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

---

Python Implementation of Cocktail Sort

def cocktail_sort(arr):
    n = len(arr)
    swapped = True
    start = 0
    end = n - 1
    
    while swapped:
        swapped = False
        
        # Traverse the list from left to right
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        
        if not swapped:
            break
        
        swapped = False
        end -= 1
        
        # Traverse the list from right to left
        for i in range(end - 1, start - 1, -1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        
        start += 1

# Example usage:
arr = [5, 3, 8, 4, 2, 7, 1, 10]
cocktail_sort(arr)
print("Sorted array:", arr)

Step-by-Step Walkthrough Example

Let’s walk through an example of Cocktail Sort with the array [5, 3, 8, 4, 2, 7, 1, 10]:

Step 1: Original array

[5, 3, 8, 4, 2, 7, 1, 10]

Step 2: Left to Right pass

• Compare 5 and 3, swap: [3, 5, 8, 4, 2, 7, 1, 10]
• Compare 5 and 8, no swap.
• Compare 8 and 4, swap: [3, 5, 4, 8, 2, 7, 1, 10]
• Compare 8 and 2, swap: [3, 5, 4, 2, 8, 7, 1, 10]
• Compare 8 and 7, swap: [3, 5, 4, 2, 7, 8, 1, 10]
• Compare 8 and 1, swap: [3, 5, 4, 2, 7, 1, 8, 10]
• Compare 8 and 10, no swap.

After the first pass:

[3, 5, 4, 2, 7, 1, 8, 10]

Step 3: Right to Left pass

• Compare 8 and 1, no swap.
• Compare 7 and 1, swap: [3, 5, 4, 2, 1, 7, 8, 10]
• Compare 4 and 2, swap: [3, 5, 2, 4, 1, 7, 8, 10]
• Compare 5 and 2, swap: [3, 2, 5, 4, 1, 7, 8, 10]
• Compare 3 and 2, swap: [2, 3, 5, 4, 1, 7, 8, 10]

After the second pass:

[2, 3, 5, 4, 1, 7, 8, 10]

Step 4: Left to Right pass

• Compare 3 and 5, no swap.
• Compare 5 and 4, swap: [2, 3, 4, 5, 1, 7, 8, 10]
• Compare 5 and 1, swap: [2, 3, 4, 1, 5, 7, 8, 10]

After the third pass:

[2, 3, 4, 1, 5, 7, 8, 10]

Step 5: Right to Left pass

• Compare 5 and 1, no swap.
• Compare 4 and 1, swap: [2, 3, 1, 4, 5, 7, 8, 10]
• Compare 3 and 1, swap: [2, 1, 3, 4, 5, 7, 8, 10]

After the fourth pass:

[2, 1, 3, 4, 5, 7, 8, 10]

Step 6: Left to Right pass

• Compare 2 and 1, swap: [1, 2, 3, 4, 5, 7, 8, 10]

After the fifth pass, no more swaps are needed, and the array is sorted.

Final sorted array:

[1, 2, 3, 4, 5, 7, 8, 10]

Performance Testing

To test Cocktail Sort’s performance, we’ll compare its behaviour on three types of arrays: random, sorted, and reverse sorted, and we’ll measure the time taken for different array sizes.

import time
import random

# Cocktail Sort implementation
def cocktail_sort(arr):
    n = len(arr)
    swapped = True
    start = 0
    end = n - 1
    
    while swapped:
        swapped = False
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        if not swapped:
            break
        swapped = False
        end -= 1
        for i in range(end - 1, start - 1, -1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        start += 1

# Function to run and time the sorting process
def test_performance(array_type, size):
    if array_type == "random":
        arr = random.sample(range(1, size + 1), size)
    elif array_type == "sorted":
        arr = list(range(1, size + 1))
    elif array_type == "reverse":
        arr = list(range(size, 0, -1))
    
    start_time = time.time()
    cocktail_sort(arr)
    end_time = time.time()
    
    return (end_time - start_time) * 1000  # Time in milliseconds

# Array sizes to test
sizes = [1000, 5000, 10000]

# Test all array types and sizes
results = {}
for array_type in ["random", "sorted", "reverse"]:
    results[array_type] = {}
    for size in sizes:
        results[array_type][size] = test_performance(array_type, size)

# Print the results
for array_type, size_results in results.items():
    print(f"Performance for {array_type} arrays:")
    for size, time_taken in size_results.items():
        print(f"Array size {size}: {time_taken:.2f} ms")

Performance Results

Array Type	Size 1000 (ms)	Size 5000 (ms)	Size 10000 (ms)
Random	51.95 ms	1152.25 ms	4900.54 ms
Sorted	0.05 ms	0.30 ms	0.57 ms
Reverse Sorted	65.87 ms	1866.85 ms	7154.78 ms

Analysis of Results

Random Arrays

• Array size 1000: 51.95 ms
• Array size 5000: 1152.25 ms
• Array size 10000: 4900.54 ms

For random arrays, Cocktail Sort’s performance scales poorly as the array size increases. With smaller arrays (like size 1000), the sort completes fairly quickly, but the time taken increases significantly as the size grows to 5000 and 10000. This is due to Cocktail Sort’s O(n²) time complexity, which causes the number of comparisons and swaps to increase quadratically as the array size grows.

• For size 5000, the performance is 22 times slower than for size 1000.
• For size 10000, the performance is almost 4.25 times slower than for size 5000.

The increasing time for larger arrays is a direct consequence of the algorithm’s quadratic behavior, making Cocktail Sort inefficient for large datasets that aren’t already partially sorted.

Sorted Arrays

• Array size 1000: 0.05 ms
• Array size 5000: 0.30 ms
• Array size 10000: 0.57 ms

For sorted arrays, Cocktail Sort performs exceptionally well. Since the array is already in order, Cocktail Sort detects this early and terminates after the first pass, leading to almost constant time performance. The time is minimal for all tested sizes, even for size 10000.

• For size 1000, the sorting completes in 0.05 ms, which is almost negligible.
• Even for size 10000, it only takes 0.57 ms, showing how quickly the algorithm detects the sorted state.

This demonstrates Cocktail Sort’s efficiency in best-case scenarios where the data is already sorted or nearly sorted, significantly outperforming the worst-case scenario.

Reverse Sorted Arrays

• Array size 1000: 65.87 ms
• Array size 5000: 1866.85 ms
• Array size 10000: 7154.78 ms

The reverse sorted arrays represent the worst-case scenario for Cocktail Sort. Every element is in the opposite position from its sorted position, meaning the algorithm has to perform the maximum number of comparisons and swaps during both left-to-right and right-to-left passes.

• For size 1000, the algorithm takes 65.87 ms, which is already slower than the random array for the same size.
• For size 5000, the time jumps to 1866.85 ms, which is approximately 28 times slower than size 1000.
• For size 10000, the time increases significantly to 7154.78 ms, making it 3.8 times slower than size 5000.

The drastic increase in time is because each element needs to be moved across the array during the alternating passes, making Cocktail Sort very inefficient when the array is in reverse order. This further illustrates the algorithm’s O(n²) complexity in the worst case, making approximately n²/2 comparisons and swaps.

Detailed Observations

1. Scaling with Array Size:
   • In the case of random and reverse arrays, we can observe the quadratic growth in time, confirming the O(n²) complexity of Cocktail Sort. As the array size increases, the time grows drastically, making Cocktail Sort unsuitable for large datasets unless they are nearly sorted.
   • The time increase is almost negligible for sorted arrays. The algorithm terminates early when no swaps are required, leading to a best-case performance of O(n), as it only needs one full pass to confirm the array is sorted.
2. Worst-case Scenario:
   • The reverse sorted array demonstrates the worst-case scenario for Cocktail Sort. In this case, every element is out of place, and the algorithm has to perform the maximum swaps and comparisons in both the forward and backward passes. This leads to excessive time complexity, making the algorithm impractical for reverse-ordered data.
3. Best-case Scenario:
   • Cocktail Sort performs extremely well when the array is already sorted. It makes one complete pass from left to right, detects no swaps are needed, and terminates early. This highlights the algorithm’s efficiency in nearly sorted datasets, where it can quickly confirm the array is already sorted without unnecessary operations.
4. Practical Consideration:
   • Due to its simplicity and bidirectional approach, Cocktail Sort can be a reasonable choice for small datasets or nearly sorted arrays. However, for large datasets or datasets that are far from being sorted (like reverse arrays), more efficient algorithms like Quick Sort, Merge Sort, or even Insertion Sort would be preferable.
   • The algorithm’s performance is closer to Bubble Sort, and the bidirectional passes provide a slight improvement over unidirectional sorting. However, the O(n²) complexity makes it unsuitable for most real-world applications where performance is a concern.

Why and How Performance Testing Results Can Vary

The performance of Cocktail Sort can vary drastically based on the initial order of the input array:

• Best-case (sorted arrays): The algorithm detects that no swaps are needed after the first pass and terminates early, resulting in an O(n) time complexity.
• Worst-case (reverse arrays): Every element is out of order, and the algorithm must perform a full pass in both directions for each element, leading to O(n²) complexity.
• Average-case (random arrays): Cocktail Sort performs reasonably well on small arrays, but its performance degrades rapidly as the array size increases due to its O(n²) complexity.

Comparing Cocktail Sort to Bubble Sort

Let’s go through the performance differences between Cocktail and Bubble sort for the sorted, reverse, and random arrays of different sizes.

import time
import random

# Cocktail Sort implementation
def cocktail_sort(arr):
    n = len(arr)
    swapped = True
    start = 0
    end = n - 1
    
    while swapped:
        swapped = False
        
        # Left to right pass
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        
        if not swapped:
            break
        
        swapped = False
        end -= 1
        
        # Right to left pass
        for i in range(end - 1, start - 1, -1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        
        start += 1

# Bubble Sort implementation
def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n):
        swapped = False
        
        # Traverse the array
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        
        # If no two elements were swapped, break
        if not swapped:
            break

# Function to run and time the sorting process
def test_sorting_algorithm(sort_func, array_type, size):
    if array_type == "random":
        arr = random.sample(range(1, size + 1), size)
    elif array_type == "sorted":
        arr = list(range(1, size + 1))
    elif array_type == "reverse":
        arr = list(range(size, 0, -1))
    
    start_time = time.time()
    sort_func(arr)
    end_time = time.time()
    
    return (end_time - start_time) * 1000  # Time in milliseconds

# Array sizes to test
sizes = [1000, 5000, 10000]

# Test all array types and sizes for Cocktail Sort and Bubble Sort
results = {"cocktail_sort": {}, "bubble_sort": {}}

for sort_name, sort_func in [("cocktail_sort", cocktail_sort), ("bubble_sort", bubble_sort)]:
    for array_type in ["random", "sorted", "reverse"]:
        results[sort_name][array_type] = {}
        for size in sizes:
            time_taken = test_sorting_algorithm(sort_func, array_type, size)
            results[sort_name][array_type][size] = time_taken
            print(f"{sort_name} on {array_type} array of size {size}: {time_taken:.2f} ms")

Performance Results: Cocktail Sort vs. Bubble Sort

Array Type	Size	Cocktail Sort (ms)	Bubble Sort (ms)
Random	1000	52.73	46.29
Random	5000	1111.63	1253.94
Random	10000	4852.40	5165.25
Sorted	1000	0.06	0.05
Sorted	5000	0.35	0.34
Sorted	10000	0.67	0.59
Reverse	1000	69.60	52.14
Reverse	5000	1928.64	1610.82
Reverse	10000	7150.77	6677.22

Summary and Analysis

Random Arrays:

• For size 1000: Bubble Sort (46.29 ms) is slightly faster than Cocktail Sort (52.73 ms).
• For size 5000: Cocktail Sort (1111.63 ms) outperforms Bubble Sort (1253.94 ms).
• For size 10000: Cocktail Sort (4852.40 ms) performs slightly better than Bubble Sort (5165.25 ms).

Analysis: For random arrays, both algorithms have similar performance, but Cocktail Sort tends to perform slightly better for larger arrays. This is likely due to its bidirectional approach, which helps reduce the number of passes in certain cases.

Sorted Arrays:

• For all array sizes, both algorithms perform extremely well, with sorting times below 1 ms. The times are nearly identical, with Bubble Sort (0.05 ms) and Cocktail Sort (0.06 ms) for size 1000 showing minimal difference.

Analysis: In the best-case scenario (already sorted arrays), both algorithms terminate early after the first pass. The performance difference is negligible, and both algorithms effectively have O(n) complexity in this case.

Reverse Arrays:

• For size 1000: Bubble Sort (52.14 ms) is faster than Cocktail Sort (69.60 ms).
• For size 5000: Bubble Sort (1610.82 ms) outperforms Cocktail Sort (1928.64 ms).
• For size 10000: Bubble Sort (6677.22 ms) is slightly faster than Cocktail Sort (7150.77 ms).

Analysis: In the worst-case scenario (reverse sorted arrays), Bubble Sort consistently outperforms Cocktail Sort. This is because Bubble Sort makes fewer unnecessary backward passes compared to Cocktail Sort, where the bidirectional approach results in more comparisons and swaps when the array is in reverse order.

Key Takeaways:

• Random Arrays: Both algorithms have similar performance, with Cocktail Sort slightly outperforming Bubble Sort as array sizes grow.
• Sorted Arrays: Both algorithms perform optimally on already sorted arrays, with negligible differences in sorting times.
• Reverse Arrays: Bubble Sort consistently outperforms Cocktail Sort in reverse sorted arrays due to fewer unnecessary backward passes.

In summary, Cocktail Sort offers slight improvements over Bubble Sort in some cases, especially for large random arrays. Still, Bubble Sort performs better in worst-case scenarios, such as reverse-sorted arrays. For already sorted data, both algorithms perform equally well.

Applications of Cocktail Sort

Cocktail Sort is rarely used in practice due to its inefficiency compared to more advanced algorithms like Quick Sort or Merge Sort. However, it is useful in educational contexts to demonstrate the concept of bidirectional sorting. It can also be employed in cases where the dataset is small and partially sorted, as it can handle nearly sorted arrays more efficiently than Bubble Sort.

Conclusion

Cocktail Sort provides an intuitive, straightforward approach to bidirectional sorting. While it improves Bubble Sort for nearly sorted arrays, its O(n²) time complexity makes it unsuitable for large datasets. Through the performance tests, we’ve seen how Cocktail Sort behaves in different scenarios. Algorithms like Quick Sort or Merge Sort are far more efficient for larger or more complex sorting tasks.

Congratulations on reading to the end of this tutorial!

For further reading on sorting algorithms in Python, go to the articles:

• How to do Insertion Sort in Python
• How to do Quick Sort in Python
• How to do Merge Sort in Python
• How to Do Selection Sort in Python
• How to do Counting Sort in Python
• How to Do Radix Sort in Python
• How to Do Bucket Sort in Python
• How to Do Heap Sort in Python
• How to Do Pigeonhole Sort in Python
• How To Do Comb Sort in Python 
• How to Do Shell Sort in Python
• How To Do TimSort in Python