sorting_rs/
bitonic_sort.rs

1/// Sorts a slice in-place using
2/// [Bitonic sort](https://en.wikipedia.org/wiki/Bitonic_sorter).
3/// All kinds of slices can be sorted as long as they implement
4/// [`PartialOrd`](https://doc.rust-lang.org/std/cmp/trait.PartialOrd.html).
5///
6/// Bitonic sort is one of the fastest sorting networks. Sorting network has the
7/// sequence of comparisons that are not data-dependent.
8/// 
9/// Default implementations of this algorithm demand power of two elements in
10/// array, but for API consistency any length is supported in case of this
11/// implementation. This flexibility comes at cost though: the least effective
12/// operation is `Vec::drain(..index)`, which removes additional values from the
13/// beginning of Vec. Also algotithm has to place new <T> instances to make
14/// array compatible with logic.
15/// 
16/// In the current implementation maximum supported array length is
17/// `9223372036854775808`. Next power of two which is `usize::MAX` is actually
18/// 2<sup>64</sup>-1, but isn't supported in most of known cases anyway, as it
19/// occupies 147.6 exabytes of memory.
20/// 
21/// Performance-wise all the available 64 bit powers of two are calculated and
22/// placed into const.
23///
24/// # Examples
25/// ```rust
26/// let mut vec = vec![5,3,2,4];
27/// sorting_rs::bitonic_sort(&mut vec);
28/// assert_eq!(vec, &[2,3,4,5]);
29/// ```
30/// ```rust
31/// let mut strings = vec!["rustc", "cargo", "rustup"];
32/// sorting_rs::bitonic_sort(&mut strings);
33/// assert_eq!(strings, &["cargo", "rustc", "rustup"]);
34/// ```
35
36pub fn bitonic_sort<T: PartialOrd + Default + Clone>(input: &mut Vec<T>) {
37    if input.len() < 2 {return;}
38    else if input.len() > 9223372036854775808 {panic!("Array is too big")}
39    
40    let in_len = input.len();
41
42    // Check if input array has length of power of 2 and add None to fill it up
43    let mut add_len = 0;
44    println!("{}", add_len);
45
46    for (i, num) in crate::POWERS_OF_TWO.iter().enumerate() {
47        if in_len == *num {add_len = 0;}
48        if i > 0 {
49            if in_len < *num {if in_len > crate::POWERS_OF_TWO[i - 1] {
50                add_len = num - in_len;}
51            }
52        }
53    }
54
55    if add_len > 0 {
56        input.append(&mut vec![T::default(); add_len]);
57    }
58    
59    bit_sort(input, true);
60    input.drain(..add_len);
61}
62
63
64fn bit_sort<T: PartialOrd>(input: &mut [T], mode: bool) {
65    if input.len() > 1 {
66        let mid_point = input.len() / 2;
67        bit_sort(&mut input[..mid_point], true);
68        bit_sort(&mut input[mid_point..], false);
69        sub_sort(input, mode);
70    }
71}
72fn sub_sort<T: PartialOrd>(input: &mut [T], mode: bool) {
73    if input.len() > 1 {
74        compare_and_swap(input, mode);
75        let mid_point = input.len() / 2;
76        sub_sort(&mut input[..mid_point], mode);
77        sub_sort(&mut input[mid_point..], mode);
78    }
79}
80fn compare_and_swap<T: PartialOrd>(input: &mut [T], mode: bool) {
81    let mid_point = input.len() / 2;
82    for i in 0..mid_point {
83        if (input[i] > input[mid_point + i]) == mode {
84            input.swap(i, mid_point + i);
85        }
86    }
87}
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92
93    #[test]
94    fn test_bitonic_usize() {
95        let mut vector_in = vec![10, 20, 11, 24, 15];
96        bitonic_sort(&mut vector_in);
97        debug_assert_eq!(vector_in, vec![10, 11, 15, 20, 24]);
98    }
99    #[test]
100    fn test_bitonic_usize_pow_2() {
101        let mut vector_in = vec![10, 20, 11, 24, 15];
102        bitonic_sort(&mut vector_in);
103        debug_assert_eq!(vector_in, vec![10, 11, 15, 20, 24]);
104    }
105    #[test]
106    fn test_bitonic_bool() {
107        let mut vector_in = vec![false, true, false, false, true];
108        bitonic_sort(&mut vector_in);
109        debug_assert_eq!(vector_in, vec![false, false, false, true, true]);
110    }
111    #[test]
112    fn test_bitonic_char() {
113        let mut vector_in = vec!['r', 'u', 's', 't', 'c'];
114        bitonic_sort(&mut vector_in);
115        debug_assert_eq!(vector_in, vec!['c', 'r', 's', 't', 'u']);
116    }
117    #[test]
118    fn test_bitonic_empty() {
119        let mut vector_in:Vec<u8> = vec![];
120        bitonic_sort(&mut vector_in);
121        debug_assert_eq!(vector_in, vec![]);
122    }
123    #[test]
124    fn test_bitonic_len1() {
125        let mut vector_in = vec![1];
126        bitonic_sort(&mut vector_in);
127        debug_assert_eq!(vector_in, vec![1]);
128    }
129}
sorting_rs/bitonic_sort.rs

sorting_rs/
bitonic_sort.rs
