sorting_rs/
selection_sort.rs

1/// Sorts a slice in-place using
2/// [Selection sort](https://en.wikipedia.org/wiki/Selection_sort).
3/// [Double selection sort](http://warp.povusers.org/DoubleBurstSelectionSort/).
4/// All kinds of slices can be sorted as long as they implement
5/// [`PartialOrd`](https://doc.rust-lang.org/std/cmp/trait.PartialOrd.html).
6///
7/// # Examples
8/// ```rust
9/// let mut vec = vec![56, 32, 78, 16];
10/// sorting_rs::selection_sort(&mut vec);
11/// assert_eq!(vec, &[16, 32, 56, 78]);
12/// ```
13/// ```rust
14/// let mut strings = vec!["rustc", "cargo", "rustup"];
15/// sorting_rs::selection_sort(&mut strings);
16/// assert_eq!(strings, &["cargo", "rustc", "rustup"]);
17/// ```
18/// ```rust
19/// let mut vec = vec![56, 32, 78, 16];
20/// sorting_rs::selection_double_sort(&mut vec);
21/// assert_eq!(vec, &[16, 32, 56, 78]);
22/// ```
23/// ```rust
24/// let mut strings = vec!["rustc", "cargo", "rustup"];
25/// sorting_rs::selection_double_sort(&mut strings);
26/// assert_eq!(strings, &["cargo", "rustc", "rustup"]);
27/// ```
28
29pub fn selection_sort<T: PartialOrd>(input: &mut [T]) {
30    if input.len() < 2 {return;}
31
32    for i in 0..input.len() {
33        let swap_val = {
34            let mut min = &input[i];
35            let mut index_min = i;
36            
37            for j in i + 1..input.len() {
38                if input[j] < *min {
39                    min = &input[j];
40                    index_min = j;
41                }
42            }
43            index_min
44        };
45
46        if i != swap_val {
47            input.swap(i, swap_val);
48        }
49    }
50}
51
52pub fn selection_double_sort<T: PartialOrd>(input: &mut [T]) {
53    if input.len() < 2 {return;}
54
55    let mut left = 0;
56    let mut right = input.len() - 1;
57    let mut min = left;
58    let mut max = left;
59
60    while left <= right {
61        for i in left..=right {
62            if input[i] > input[max] {
63                max = i;
64            }
65            if input[i] < input[min] {
66                min = i;
67            }
68        }
69        if max == left {max = min;}
70        input.swap(left, min);
71        input.swap(right, max);
72
73        left += 1;
74        right -= 1;
75
76        min = left;
77        max = right;
78    }
79}
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84
85    #[test]
86    fn test_selection() {
87        let mut vector_in = vec![11, 20, 21, 40, 11, 60, 5];
88        selection_sort(&mut vector_in);
89        debug_assert_eq!(vector_in, vec![5, 11, 11, 20, 21, 40, 60]);
90    }
91    #[test]
92    fn test_selection_empty() {
93        let mut vector_in:Vec<i32> = vec![];
94        selection_sort(&mut vector_in);
95        debug_assert_eq!(vector_in, &[]);
96    }
97    #[test]
98    fn test_selection_len1() {
99        let mut vector_in = vec![1];
100        selection_sort(&mut vector_in);
101        debug_assert_eq!(vector_in, vec![1]);
102    }
103    #[test]
104    fn test_selection_double() {
105        let mut vector_in = vec![11, 20, 21, 40, 11, 60, 5];
106        selection_double_sort(&mut vector_in);
107        debug_assert_eq!(vector_in, vec![5, 11, 11, 20, 21, 40, 60]);
108    }
109    #[test]
110    fn test_selection_double_empty() {
111        let mut vector_in:Vec<i32> = vec![];
112        selection_double_sort(&mut vector_in);
113        debug_assert_eq!(vector_in, &[]);
114    }
115    #[test]
116    fn test_selection_double_len1() {
117        let mut vector_in = vec![1];
118        selection_double_sort(&mut vector_in);
119        debug_assert_eq!(vector_in, vec![1]);
120    }
121}
sorting_rs/selection_sort.rs

sorting_rs/
selection_sort.rs
