sort/
lib.rs

1pub fn bubble_sort<T: PartialOrd>(list: &mut [T]) {
2    let size = list.len();
3    for i in 0..(size - 1) {
4        let mut swapped = false;
5        for j in 0..(size - 1 - i) {
6            if list[j] > list[j + 1] {
7                list.swap(j, j + 1);
8                swapped = true;
9            }
10        }
11        if !swapped {
12            break;
13        }
14    }
15}
16
17pub fn selection_sort<T: PartialOrd>(list: &mut [T]) {
18    let size = list.len();
19    for i in 0..(size - 1) {
20        let mut min_index = i;
21        for j in (i + 1)..(size) {
22            if list[j] < list[min_index] {
23                min_index = j;
24            }
25        }
26        list.swap(min_index, i);
27    }
28}
29
30pub fn insertion_sort<T: PartialOrd + Copy>(list: &mut [T]) {
31    for i in 1..(list.len()) {
32        let key = list[i];
33        let mut j = (i - 1) as i32;
34        while j >= 0 && list[j as usize] > key {
35            list[(j + 1) as usize] = list[j as usize];
36            j -= 1;
37        }
38        list[(j + 1) as usize] = key;
39    }
40}
41
42fn merge<T: PartialOrd + Copy>(first_half: &[T], second_half: &[T], list: &mut [T]) {
43    let s1 = first_half.len();
44    let s2 = second_half.len();
45    let mut i1 = 0_usize;
46    let mut i2 = 0_usize;
47    let mut counter = 0_usize;
48    loop {
49        if i1 >= s1 {
50            while i2 < s2 {
51                list[counter] = second_half[i2];
52                i2 += 1;
53                counter += 1;
54            }
55            break;
56        } else if i2 >= s2 {
57            while i1 < s1 {
58                list[counter] = first_half[i1];
59                i1 += 1;
60                counter += 1;
61            }
62            break;
63        }
64        if first_half[i1] <= second_half[i2] {
65            list[counter] = first_half[i1];
66            i1 += 1;
67        } else {
68            list[counter] = second_half[i2];
69            i2 += 1;
70        }
71        counter += 1;
72    }
73}
74
75pub fn merge_sort<T: PartialOrd + Copy>(list: &mut [T]) {
76    let mid = list.len() / 2;
77    if mid == 0 {
78        return;
79    }
80    merge_sort(&mut list[..mid]);
81    merge_sort(&mut list[mid..]);
82
83    let mut res = list.to_vec();
84    merge(&list[..mid], &list[mid..], &mut res);
85
86    list.copy_from_slice(&res);
87}
88
89fn partition<T: PartialOrd + Copy>(list: &mut [T], left_most: i32, right_most: i32) -> i32 {
90    let pivot = list[right_most as usize];
91    let mut i = left_most - 1;
92    let rm_usize = right_most as usize;
93    let lm_usize = left_most as usize;
94
95    for j in lm_usize..(rm_usize + 1) {
96        if list[j] < pivot {
97            i += 1;
98            list.swap(i as usize, j);
99        }
100    }
101    list.swap((i + 1) as usize, rm_usize);
102    return i + 1;
103}
104
105fn recursive_quick_sort<T: PartialOrd + Copy>(list: &mut [T], left_most: i32, right_most: i32) {
106    if left_most < right_most {
107        let p_index = partition(list, left_most, right_most);
108        recursive_quick_sort(list, left_most, p_index - 1);
109        recursive_quick_sort(list, p_index + 1, right_most);
110    }
111}
112
113pub fn quick_sort<T: PartialOrd + Copy>(list: &mut [T]) {
114    recursive_quick_sort(list, 0, list.len() as i32 - 1);
115}
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120    #[test]
121    fn test_bubble_sort() {
122        let mut v = [3, 2, 5, 6, 1, 4];
123        bubble_sort(&mut v);
124        assert_eq!(v, [1, 2, 3, 4, 5, 6]);
125    }
126
127    #[test]
128    fn test_selection_sort() {
129        let mut v = [4, 6, 3, 1, 5, 2];
130        selection_sort(&mut v);
131        assert_eq!(v, [1, 2, 3, 4, 5, 6]);
132    }
133
134    #[test]
135    fn test_insertion_sort() {
136        let mut v = [1, 5, 3, 6, 2, 4];
137        insertion_sort(&mut v);
138        assert_eq!(v, [1, 2, 3, 4, 5, 6]);
139    }
140
141    #[test]
142    fn test_merge_sort() {
143        let mut v = [2, 3, 4, 1, 6, 5];
144        merge_sort(&mut v);
145        assert_eq!(v, [1, 2, 3, 4, 5, 6]);
146    }
147
148    #[test]
149    fn test_quick_sort() {
150        let mut v = [6, 1, 2, 5, 4, 3];
151        quick_sort(&mut v);
152        assert_eq!(v, [1, 2, 3, 4, 5, 6]);
153    }
154}
sort/lib.rs

sort/
lib.rs
