sorting_algorithm/
quick_sort.rs

1use fastrand;
2
3/// Sorts a data set using Quick Sort
4///
5/// # Examples
6///
7/// ```
8/// use sorting_algorithm::quick_sort;
9///
10/// fn main() {
11///     let mut data = [3, 1, 2, 5, 4];
12///     
13///     quick_sort::sort(&mut data);
14///
15///     assert_eq!(data, [1, 2, 3, 4, 5]);
16/// }
17/// ```
18pub fn sort<T: Ord>(data: &mut [T]) {
19    if data.len() > 1 {
20        let pivot = partition(data);
21
22        sort(&mut data[..pivot]);
23        sort(&mut data[pivot + 1..]);
24    }
25}
26
27fn partition<T: Ord>(data: &mut [T]) -> usize {
28    let n = data.len();
29    let pivot = fastrand::usize(0..data.len());
30    data.swap(pivot, n - 1);
31
32    let mut i = 0;
33
34    for j in 0..n - 1 {
35        if data[j] <= data[n - 1] {
36            data.swap(i, j);
37            i += 1;
38        }
39    }
40
41    data.swap(i, n - 1);
42    i
43}
sorting_algorithm/quick_sort.rs

sorting_algorithm/
quick_sort.rs
