How To Do Cocktail Sort in Rust

Cocktail Sort, or Bidirectional Bubble Sort or Shaker Sort, is a variation of the traditional Bubble Sort. Instead of traversing the list in one direction, Cocktail Sort traverses the list in both directions, alternating between left and right to left. This helps slightly improve efficiency compared to Bubble Sort, especially for partially sorted lists. In this blog post will implement Cocktail Sort in Rust, explain its time and space complexity, and compare it to Bubble Sort and Quick Sort.

What is Cocktail Sort?

Cocktail Sort is a comparison-based, stable sorting algorithm that works by alternately passing through the array in both directions. During the forward pass, it “bubbles” the largest elements to the end of the list, and during the backward pass, it “bubbles” the smallest elements to the front.

Key Steps in Cocktail Sort:

1. Forward Pass: Move from left to right, bubbling the largest unsorted element to the end of the array.
2. Backward Pass: Move from right to left, bubbling the smallest unsorted element to the beginning of the array.
3. Repeat the above steps until the list is sorted.

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.

Time Complexity of Cocktail Sort

• Best Case (Nearly Sorted Data): O(n) — If the array is nearly sorted, Cocktail Sort may complete in linear time.
• Average Case: O(n²) — Like Bubble Sort, Cocktail Sort requires O(n²) comparisons and swaps in the average case.
• Worst Case: O(n²) — If the array is in reverse order, Cocktail Sort will require multiple passes to sort it completely.

Space Complexity of Cocktail Sort

Cocktail Sort is an in-place sorting algorithm, meaning it doesn’t require any extra memory beyond the input array. Its space complexity is O(1).

Pseudocode for Cocktail Sort

Here’s the high-level pseudocode for Cocktail Sort:

function cocktailSort(arr):
    swapped = true
    start = 0
    end = length(arr) - 1

    while swapped:
        swapped = false
        
        // Forward pass
        for i from start to end - 1:
            if arr[i] > arr[i + 1]:
                swap(arr[i], arr[i + 1])
                swapped = true
        
        // If nothing was swapped, then the array is sorted
        if not swapped:
            break

        swapped = false
        end = end - 1

        // Backward pass
        for i from end - 1 to start:
            if arr[i] > arr[i + 1]:
                swap(arr[i], arr[i + 1])
                swapped = true

        start = start + 1

Rust Implementation of Cocktail Sort

Let’s implement Cocktail Sort in Rust, taking advantage of Rust’s ownership and borrowing principles to ensure safe memory usage.

Rust Code for Cocktail Sort

fn cocktail_sort<T: Ord>(arr: &mut [T]) {
    let mut swapped = true;
    let mut start = 0;
    let mut end = arr.len();

    while swapped {
        swapped = false;

        // Forward pass
        for i in start..end - 1 {
            if arr[i] > arr[i + 1] {
                arr.swap(i, i + 1);
                swapped = true;
            }
        }

        if !swapped {
            break;
        }

        swapped = false;
        end -= 1;

        // Backward pass
        for i in (start..end - 1).rev() {
            if arr[i] > arr[i + 1] {
                arr.swap(i, i + 1);
                swapped = true;
            }
        }

        start += 1;
    }
}

fn main() {
    let mut numbers = vec![5, 1, 4, 2, 8, 0, 2];
    println!("Before sorting: {:?}", numbers);
    cocktail_sort(&mut numbers);
    println!("After sorting: {:?}", numbers);
}

Output:

Before sorting: [5, 1, 4, 2, 8, 0, 2]
After sorting: [0, 1, 2, 2, 4, 5, 8]

Rust Specifics in Cocktail Sort Implementation

1. In-place Swapping with swap(): Rust’s built-in swap() method allows us to swap elements in place without violating ownership or borrowing rules.
2. Mutable References: Cocktail Sort operates on a mutable reference to the array, ensuring safe, in-place modification.
3. Range Iteration and .rev(): Rust’s flexible iterator system lets us easily traverse arrays in both directions with the .rev() method for reverse iteration.
4. Generic Type Bounds (Ord): Rust’s trait system lets us write sorting functions that work with any type implementing the Ord trait. The Ord trait allows types to be compared using operators like <, >, <=, and >=. In Cocktail Sort, we need comparisons in both the forward and backward passes, so we include T: Ord in the function signature to ensure the elements can be compared and sorted.

Step-by-Step Explanation of Cocktail Sort with Example

Let’s walk through each step of the Cocktail Sort process using the array [5, 1, 4, 2, 8, 0, 2].

Initial Array:

[5, 1, 4, 2, 8, 0, 2]

---

Step 1: Forward Pass

We start by traversing from left to right. The goal is to bubble the largest element to the rightmost position in this pass.

1. Compare 5 and 1. Since 5 > 1, we swap.
   • Array after swap: [1, 5, 4, 2, 8, 0, 2]
2. Compare 5 and 4. Since 5 > 4, we swap.
   • Array after swap: [1, 4, 5, 2, 8, 0, 2]
3. Compare 5 and 2. Since 5 > 2, we swap.
   • Array after swap: [1, 4, 2, 5, 8, 0, 2]
4. Compare 5 and 8. No swap needed, since 5 < 8.
5. Compare 8 and 0. Since 8 > 0, we swap.
   • Array after swap: [1, 4, 2, 5, 0, 8, 2]
6. Compare 8 and 2. Since 8 > 2, we swap.
   • Array after swap: [1, 4, 2, 5, 0, 2, 8]

At the end of this pass, the largest element (8) is bubbled to its correct position at the end.

---

Step 2: Backward Pass

Now, we traverse from right to left. The goal is to bubble the smallest element to the leftmost position.

1. Compare 2 and 0. Since 2 > 0, we swap.
   • Array after swap: [1, 4, 2, 5, 0, 2, 8]
2. Compare 5 and 0. Since 5 > 0, we swap.
   • Array after swap: [1, 4, 2, 0, 5, 2, 8]
3. Compare 2 and 0. Since 2 > 0, we swap.
   • Array after swap: [1, 4, 0, 2, 5, 2, 8]
4. Compare 4 and 0. Since 4 > 0, we swap.
   • Array after swap: [1, 0, 4, 2, 5, 2, 8]
5. Compare 1 and 0. Since 1 > 0, we swap.
   • Array after swap: [0, 1, 4, 2, 5, 2, 8]

At the end of this pass, the smallest element (0) is bubbled to the leftmost position.

---

Step 3: Forward Pass

We now start the forward pass again from the second position (index 1) since the smallest element is already in place.

1. Compare 1 and 4. No swap needed, since 1 < 4.
2. Compare 4 and 2. Since 4 > 2, we swap.
   • Array after swap: [0, 1, 2, 4, 5, 2, 8]
3. Compare 4 and 5. No swap needed, since 4 < 5.
4. Compare 5 and 2. Since 5 > 2, we swap.
   • Array after swap: [0, 1, 2, 4, 2, 5, 8]

At the end of this pass, the second-largest element (5) is now in its correct position.

---

Step 4: Backward Pass

We perform another backward pass, starting from the position before the last swapped element.

1. Compare 4 and 2. Since 4 > 2, we swap.
   • Array after swap: [0, 1, 2, 2, 4, 5, 8]
2. Compare 2 and 2. No swap needed, since they are equal.

At the end of this pass, no further swaps are needed, so the array is considered sorted.

---

Final Array:

[0, 1, 2, 2, 4, 5, 8]

---

Summary of Steps:

• Step 1 (Forward): The largest element (8) was bubbled to the end of the array.
• Step 2 (Backward): The smallest element (0) was bubbled to the start of the array.
• Step 3 (Forward): The second-largest element (5) was moved to its correct position.
• Step 4 (Backward): The final necessary swaps sorted the array.

Cocktail Sort alternates between forward and backward passes until no further swaps are needed. At this point, the array is sorted. This bidirectional approach allows Cocktail Sort to potentially reduce the number of passes needed compared to a traditional Bubble Sort.

Performance Test: Cocktail Sort vs Bubble Sort vs Quick Sort

To better understand how Cocktail Sort performs, let’s compare it against Bubble Sort and Quick Sort with random, sorted, and reverse-sorted arrays of 1000, 5000, and 10000. While both Cocktail Sort and Bubble Sort have O(n²) time complexity, Cocktail Sort is expected to perform better in cases where the array is partially sorted due to its bidirectional pass. On the other hand, with its average time complexity of O(n log n), Quick Sort is generally expected to outperform both in most cases, especially for larger datasets. However, its performance may degrade for specific cases like reverse-sorted data without optimizations like median-of-three.

We’ll use Rust’s std::time::Instant for benchmarking and for generating arrays, we can utilize the rand crate to create random arrays and manual loops to generate sorted and reverse-sorted arrays.

When performing your tests, include rand in the under the [dependencies] section of your Cargo.toml file, for example:

[package]
name = "insertion_sort"
version = "0.1.0"
edition = "2021"

[dependencies]
rand = "0.9.0-alpha.2"

Rust Code for Performance Test

use rand::seq::SliceRandom;
use std::time::Instant;

// Cocktail Sort Implementation
fn cocktail_sort<T: Ord>(arr: &mut [T]) {
    let mut swapped = true;
    let mut start = 0;
    let mut end = arr.len();

    while swapped {
        swapped = false;

        // Forward pass
        for i in start..end - 1 {
            if arr[i] > arr[i + 1] {
                arr.swap(i, i + 1);
                swapped = true;
            }
        }

        if !swapped {
            break;
        }

        swapped = false;
        end -= 1;

        // Backward pass
        for i in (start..end - 1).rev() {
            if arr[i] > arr[i + 1] {
                arr.swap(i, i + 1);
                swapped = true;
            }
        }

        start += 1;
    }
}

// Bubble Sort Implementation
fn bubble_sort<T: Ord>(arr: &mut [T]) {
    let mut swapped = true;
    while swapped {
        swapped = false;
        for i in 0..arr.len() - 1 {
            if arr[i] > arr[i + 1]) {
                arr.swap(i, i + 1);
                swapped = true;
            }
        }
    }
}

// Quick Sort Implementation
fn quick_sort<T: Ord>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return;
    }

    let pivot_index = partition(arr);
    let (left, right) = arr.split_at_mut(pivot_index);
    quick_sort(left);
    quick_sort(&mut right[1..]);
}

// Partition function for Quick Sort
fn partition<T: Ord>(arr: &mut [T]) -> usize {
    let pivot_index = arr.len() - 1;
    let mut i = 0;

    for j in 0..pivot_index {
        if arr[j] < arr[pivot_index] {
            arr.swap(i, j);
            i += 1;
        }
    }
    arr.swap(i, pivot_index);
    i
}

// Benchmarking Function
fn benchmark(sort_fn: fn(&mut [i32]), arr: &mut [i32], name: &str) {
    let start = Instant::now();
    sort_fn(arr);
    let duration = start.elapsed();
    println!("{}: {:?}", name, duration);
}

fn main() {
    let mut rng = rand::thread_rng();
    let sizes = [1000, 5000, 10000];

    for &size in &sizes {
        println!("\nArray size: {}", size);

        // Random array
        let mut arr: Vec<i32> = (0..size).collect();
        arr.shuffle(&mut rng);
        benchmark(cocktail_sort, &mut arr.clone(), "Cocktail Sort (random)");
        benchmark(bubble_sort, &mut arr.clone(), "Bubble Sort (random)");
        benchmark(quick_sort, &mut arr.clone(), "Quick Sort (random)");

        // Sorted array
        arr.sort();
        benchmark(cocktail_sort, &mut arr.clone(), "Cocktail Sort (sorted)");
        benchmark(bubble_sort, &mut arr.clone(), "Bubble Sort (sorted)");
        benchmark(quick_sort, &mut arr.clone(), "Quick Sort (sorted)");

        // Reverse sorted array
        arr.reverse();
        benchmark(cocktail_sort, &mut arr.clone(), "Cocktail Sort (reverse)");
        benchmark(bubble_sort, &mut arr.clone(), "Bubble Sort (reverse)");
        benchmark(quick_sort, &mut arr.clone(), "Quick Sort (reverse)");
    }
}

Results

Cocktail Sort vs Bubble Sort vs Quick Sort Performance (in milliseconds)

Array Size & Configuration	Cocktail Sort	Bubble Sort	Quick Sort
1000 (Random)	22.3	33.0	1.0
1000 (Sorted)	0.013	0.013	37.0
1000 (Reverse)	35.0	51.1	26.0
5000 (Random)	697.3	851.1	2.5
5000 (Sorted)	0.052	0.052	616.7
5000 (Reverse)	645.7	752.7	391.0
10000 (Random)	1644.9	2608.1	6.8
10000 (Sorted)	0.126	0.126	2888.6
10000 (Reverse)	3098.6	3532.9	1850.7

Note: Times are rounded to one decimal place for readability. Actual performance may vary slightly due to system-specific factors.

Analysis of Results

• Cocktail Sort vs Bubble Sort:
  • Cocktail Sort consistently outperforms Bubble Sort, especially on random and reverse-sorted data, making it a better alternative for small to medium datasets.
• Quick Sort:
  • Quick Sort dominates Cocktail Sort and Bubble Sort on random data but suffers on sorted data due to its poor handling of already sorted arrays. It is important to note that this Quick Sort implementation has not been optimized with techniques like median-of-three pivot selection, which would improve its performance on already sorted or reverse-sorted data. Even without optimizations, Quick Sort performs better than Cocktail Sort and Bubble Sort on large random and reverse-sorted arrays.
• Small Dataset Performance:
  • Both Cocktail Sort and Bubble Sort perform admirably for small datasets or sorted data. However, despite its potential worst-case pitfalls, Quick Sort is the winner for large random or reverse-sorted datasets.

Pros and Cons of Cocktail Sort

Pros

• Improved Efficiency Over Bubble Sort: Cocktail Sort’s bidirectional nature reduces the number of passes required compared to Bubble Sort, making it more efficient in some cases.
• In-Place and Stable: Cocktail Sort does not require additional memory and maintains the stability of the sorted elements.

Cons

• Still O(n²) in Average and Worst Case: Cocktail Sort, like Bubble Sort, still has a quadratic time complexity in the average and worst cases, making it inefficient for large datasets.
• Complexity Overhead: The forward and backward passes add extra complexity compared to Bubble Sort without significantly improving the performance in all scenarios.

When to Use Cocktail Sort

• For small datasets (typically n < 50), simpler algorithms like Insertion Sort or Cocktail Sort can outperform more complex ones due to lower overhead.
• For medium to large datasets, algorithms like Quick Sort, Merge Sort, or Heap Sort are generally preferred due to their O(n log n) average time complexity.
• Some hybrid algorithms, like Introsort (used in many standard library implementations), combine the benefits of Quick Sort with a worst-case O(n log n) guarantee.

Conclusion

Cocktail Sort offers an optimized version of Bubble Sort, excelling with small, nearly sorted datasets due to its bidirectional approach. As a stable, in-place algorithm, it addresses some inefficiencies of standard Bubble Sort. However, its O(n²) time complexity limits its usefulness for larger datasets, where algorithms like Quick Sort, Merge Sort, or Heap Sort are preferable due to their O(n log n) average-case performance. While Cocktail Sort may not be the primary choice for general sorting needs, understanding its mechanics provides valuable insights into algorithm optimization and the trade-offs in sorting algorithm design.

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 C++ – How to Do Cocktail Sort in C++

In JavaScript – How to do Cocktail Sort in JavaScript

Have fun and happy researching!