ndsort_rs/
lib.rs

1pub mod sorting {
2    pub fn bubble_sort<T: PartialOrd>(arr: &mut [T]) {
3        let mut swapped = true;
4        let mut end = arr.len() - 1;
5
6        while swapped {
7            swapped = false;
8            for i in 0..end {
9                if arr[i] > arr[i + 1] {
10                    arr.swap(i, i + 1);
11                    swapped = true;
12                }
13            }
14            end -= 1;
15        }
16    }
17
18    pub fn shell_sort<T: PartialOrd>(arr: &mut [T]) {
19        let n = arr.len();
20        let mut h = 1;
21        while h < n / 3 {
22            h = 3 * h + 1;
23        }
24        while h >= 1 {
25            for i in h..n {
26                let mut j = i;
27                while j >= h && arr[j] < arr[j - h] {
28                    arr.swap(j, j - h);
29                    j -= h;
30                }
31            }
32            h /= 3;
33        }
34    }
35
36    pub fn heap_sort<T: PartialOrd>(arr: &mut [T]) {
37        let n = arr.len();
38
39        for i in (0..n / 2).rev() {
40            heapify(arr, n, i);
41        }
42
43        for i in (1..n).rev() {
44            arr.swap(0, i);
45            heapify(arr, i, 0);
46        }
47    }
48
49    fn heapify<T: PartialOrd>(arr: &mut [T], n: usize, i: usize) {
50        let mut largest = i;
51        let left = 2 * i + 1;
52        let right = 2 * i + 2;
53        if left < n && arr[left] > arr[largest] {
54            largest = left;
55        }
56
57        if right < n && arr[right] > arr[largest] {
58            largest = right;
59        }
60        if largest != i {
61            arr.swap(i, largest);
62            heapify(arr, n, largest);
63        }
64    }
65
66    pub fn quick_sort<T: PartialOrd + Copy>(arr: &mut [T]) {
67        let len = arr.len();
68        if len > 1 {
69            let pivot = partition(arr);
70            quick_sort(&mut arr[0..pivot]);
71            quick_sort(&mut arr[pivot + 1..len]);
72        }
73    }
74
75    fn partition<T: PartialOrd + Copy>(arr: &mut [T]) -> usize {
76        let len = arr.len();
77        let pivot_index = len / 2;
78        let last_index = len - 1;
79
80        arr.swap(pivot_index, last_index);
81        let mut store_index = 0;
82        for i in 0..last_index {
83            if arr[i] < arr[last_index] {
84                arr.swap(i, store_index);
85                store_index += 1;
86            }
87        }
88        arr.swap(store_index, last_index);
89        store_index
90    }
91
92    pub fn merge_sort<T: Ord + Copy>(arr: &mut [T]) {
93        let len = arr.len();
94        if len <= 1 {
95            return;
96        }
97        let mid = len / 2;
98        merge_sort(&mut arr[..mid]);
99        merge_sort(&mut arr[mid..]);
100        let mut temp = Vec::with_capacity(len);
101        let (mut i, mut j) = (0, mid);
102        while i < mid && j < len {
103            if arr[i] <= arr[j] {
104                temp.push(arr[i]);
105                i += 1;
106            } else {
107                temp.push(arr[j]);
108                j += 1;
109            }
110        }
111        temp.extend_from_slice(&arr[i..mid]);
112        temp.extend_from_slice(&arr[j..]);
113        arr.copy_from_slice(&temp);
114    }
115}
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120    use crate::sorting::*;
121    use rand::Rng;
122
123    #[test]
124    fn test_bubble_sort() {
125        let mut rng = rand::thread_rng();
126        let arr = [0; 10000];
127        let mut arr = arr.map(|_| rng.gen_range(0..1000));
128        assert_eq!(arr.sort(), bubble_sort(&mut arr))
129    }
130
131    #[test]
132    fn test_shell_sort() {
133        let mut rng = rand::thread_rng();
134        let arr = [0; 10000];
135        let mut arr = arr.map(|_| rng.gen_range(0..1000));
136        assert_eq!(arr.sort(), shell_sort(&mut arr))
137    }
138
139    #[test]
140    fn test_heap_sort() {
141        let mut rng = rand::thread_rng();
142        let arr = [0; 10000];
143        let mut arr = arr.map(|_| rng.gen_range(0..1000));
144        let mut lettere = ['b', 'a', 'c'];
145        assert_eq!(arr.sort(), heap_sort(&mut arr));
146        assert_eq!(lettere.sort(), heap_sort(&mut lettere))
147    }
148}
ndsort_rs/lib.rs

ndsort_rs/
lib.rs
