sorting_algorithm/
quick_sort.rs

1use fastrand;
2
3pub fn sort<T: Ord>(data: &mut [T]) {
4    if data.len() > 1 {
5        let pivot = partition(data);
6
7        sort(&mut data[..pivot]);
8        sort(&mut data[pivot + 1..]);
9    }
10}
11
12fn partition<T: Ord>(data: &mut [T]) -> usize {
13    let n = data.len();
14    let pivot = fastrand::usize(0..data.len());
15    data.swap(pivot, n - 1);
16
17    let mut i = 0;
18
19    for j in 0..n - 1 {
20        if data[j] <= data[n - 1] {
21            data.swap(i, j);
22            i += 1;
23        }
24    }
25
26    data.swap(i, n - 1);
27    i
28}