algorithmplus 0.1.4

Library of commonly used algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

/// Sort an array using quick sort
///
/// # Parameters
///
/// - `arr`: A vector to sort in-place
///
/// # Type parameters
///
/// - `T`: A type that can be checked for equality and ordering e.g. a `i32`, a
///     `u8`, or a `f32`.
///
/// # Undefined Behavior
/// 
/// Does not work with `String` vectors.
/// 
/// # Examples
///
/// ```rust
/// use algorithmplus::sort::quick_sort;
/// 
/// let mut ls = vec![3, 2, 1];
/// quick_sort(&mut ls);
/// 
/// assert_eq!(ls, [1, 2, 3]);
/// ```

pub fn quick_sort<T: PartialEq + PartialOrd + Copy> (arr: &mut [T]) {
    _quick_sort(arr, 0, arr.len() as isize - 1);
}

fn _quick_sort<T: PartialEq + PartialOrd + Copy> (arr: &mut [T], low: isize, high: isize) {
    if low < high {
        let pi = partition(arr, low, high);

        _quick_sort(arr, low, pi - 1);
        _quick_sort(arr, pi + 1, high);
    }
}

fn partition<T: PartialEq + PartialOrd + Copy> (arr: &mut [T], low: isize, high: isize) -> isize {
    let pivot = arr[high as usize];
    let mut i = low - 1;

    for j in low..high {
        if arr[j as usize] < pivot {
            i += 1;
            arr.swap(i as usize, j as usize);
        }
    }

    arr.swap((i + 1) as usize, high as usize);
    i + 1
}