rust_sort/
cocktail_sort.rs

1use super::Sortable;
2
3/// Cocktail sorts in-place, stable, in ascending order a mutable ref slice of type T: Sortable
4///
5/// Cocktail is a variant of bubble sort. It continuously loops over elements in slice collection, swapping elements
6/// if they are out of order. If no swaps occur in a loop then the sort is complete.
7/// Each iteration swaps order of the iteration from left to right and from comparing smallest to largest, such that
8/// the largest and smallest elements are bubbled up and down the list bidirectionally.
9/// It aims to solve the rabbit and turtle problem of standard bubble sort where values that
10/// need to move to the beginning of the list require many swaps to get there.
11///
12/// # Examples
13///
14/// ```
15/// use rust_sort::cocktail_sort::sort;
16///
17/// let mut arr = [3, 2, 1, 7, 9, 4, 1, 2];
18/// sort(&mut arr);
19/// assert_eq!(arr, [1, 1, 2, 2, 3, 4, 7, 9]);
20///
21/// ```
22pub fn sort<T: Sortable>(list: &mut [T]) {
23    let len = list.len();
24    if len <= 1 {
25        return;
26    }
27
28    loop {
29        let mut swapped = false;
30        for i in 0..len - 1 {
31            if list[i] > list[i + 1] {
32                list.swap(i, i + 1);
33                swapped = true;
34            }
35        }
36        if !swapped {
37            break;
38        }
39        for i in (1..len-1).rev() {
40            if list[i] < list[i - 1] {
41                list.swap(i, i - 1);
42                swapped = true;
43            }
44        }
45        if !swapped {
46            break;
47        }
48    }
49}
rust_sort/cocktail_sort.rs

rust_sort/
cocktail_sort.rs
