qsort_rs/
qsort.rs

1/// A quick sort function that accepts any type using non-recursive approach.
2pub fn sort<T: Ord>(array: &mut [T], compare: impl Fn(&T, &T) -> bool) {
3    if array.len() < 2 {
4        return;
5    }
6
7    let mut stack = Vec::new();
8    stack.push((0, array.len()));
9
10    while let Some((low, high)) = stack.pop() {
11        if high - low > 1 {
12            let pivot = partition(array, low, high, &compare);
13            stack.push((low, pivot));
14            stack.push((pivot + 1, high));
15        }
16    }
17}
18
19fn partition<T: Ord>(
20    array: &mut [T],
21    low: usize,
22    high: usize,
23    compare: impl Fn(&T, &T) -> bool,
24) -> usize {
25    let pivot = low + (high - low) / 2;
26    array.swap(pivot, high - 1);
27
28    let mut i = low;
29    for j in low..high - 1 {
30        if compare(&array[j], &array[high - 1]) {
31            array.swap(i, j);
32            i += 1;
33        }
34    }
35    array.swap(i, high - 1);
36    i
37}
qsort_rs/qsort.rs

qsort_rs/
qsort.rs
