algorithms/sorting/
quick_sort.rs

1fn _partition<T: Ord>(arr: &mut [T], lo: isize, hi: isize) -> isize {
2    let pivot = hi as usize;
3    let mut i = lo - 1;
4    let mut j = hi;
5
6    loop {
7        i += 1;
8        while arr[i as usize] < arr[pivot] {
9            i += 1;
10        }
11        j -= 1;
12        while j >= 0 && arr[j as usize] > arr[pivot] {
13            j -= 1;
14        }
15        if i >= j {
16            break;
17        } else {
18            arr.swap(i as usize, j as usize);
19        }
20    }
21    arr.swap(i as usize, pivot as usize);
22    i
23}
24fn _quick_sort<T: Ord>(arr: &mut [T], lo: isize, hi: isize) {
25    if lo < hi {
26        let p = _partition(arr, lo, hi);
27        _quick_sort(arr, lo, p - 1);
28        _quick_sort(arr, p + 1, hi);
29    }
30}
31pub fn quick_sort<T: Ord>(arr: &mut [T]) {
32    let len = arr.len();
33    _quick_sort(arr, 0, (len - 1) as isize);
34}
algorithms/sorting/quick_sort.rs

algorithms/sorting/
quick_sort.rs
