quick_sort 0.2.1

In place quick sort
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

//! A standard in-place quick sort using a median of
//! first, middle and last element in each slice for the pivot.


/// # Example
///
/// ```
/// let mut numbers = vec![12, 2, -9, -45, 0, 67];
/// quick_sort::sort(numbers.as_mut_slice());
/// ```

use std::cmp::Ordering;

pub fn sort<T>(arr: &mut [T])
    where T: std::cmp::PartialEq + Ord
{
    qsort(arr, find_pivot, &|a, b| a.cmp(b))
}


/// # Example
///
/// ```
/// let mut numbers = vec![12, 2, -9, -45, 0, 67];
/// quick_sort::sort_by(numbers.as_mut_slice(), &|a, b| b.cmp(a));
/// ```
pub fn sort_by<T, F>(arr: &mut [T], compare: &F)
    where T: std::cmp::PartialOrd,
          F: Fn(&T, &T) -> Ordering
{
    qsort(arr, find_pivot, compare);
}

fn qsort<T, F>(arr: &mut [T], pivot: fn(&[T], &F) -> usize, compare: &F)
    where T: std::cmp::PartialOrd,
          F: Fn(&T, &T) -> Ordering
{
    let len = arr.len();
    if len <= 1 {
        return;
    }

    let p = pivot(arr, compare);
    let p = partition(arr, p, compare);
    if p > len / 2 {
        qsort(&mut arr[p + 1..len], pivot, compare);
        qsort(&mut arr[0..p], pivot, compare);
    } else {
        qsort(&mut arr[0..p], pivot, compare);
        qsort(&mut arr[p + 1..len], pivot, compare);
    }
}

fn find_pivot<T, F>(arr: &[T], compare: &F) -> usize
    where T: std::cmp::PartialOrd,
          F: Fn(&T, &T) -> Ordering
{
    let (l, r) = (0, arr.len() - 1);
    let m = l + ((r - 1) / 2);
    let (left, middle, right) = (&arr[l], &arr[m], &arr[r]);
    if (compare(middle, left) != Ordering::Less) && (compare(middle, right) != Ordering::Greater) {
        m
    } else if (compare(left, middle) != Ordering::Less) &&
              (compare(left, right) != Ordering::Greater) {
        l
    } else {
        r
    }
}


fn partition<T, F>(arr: &mut [T], p: usize, compare: &F) -> usize
    where T: std::cmp::PartialOrd,
          F: Fn(&T, &T) -> Ordering
{
    if arr.len() <= 1 {
        return p;
    }

    let last = arr.len() - 1;
    let mut next_pivot = 0;
    arr.swap(last, p);
    for i in 0..last {
        if compare(&arr[i], &arr[last]) == Ordering::Less {
            arr.swap(i, next_pivot);
            next_pivot += 1;
        }
    }

    arr.swap(next_pivot, last);
    next_pivot
}

#[cfg(test)]
mod test {
    extern crate rand;
    use super::sort;
    use super::sort_by;

    #[test]
    fn test_random_sequece_default_order() {
        let mut numbers = Vec::new();
        for _ in 1..1000 {
            numbers.push(rand::random::<i32>());
        }

        sort(numbers.as_mut_slice());

        for i in 0..numbers.len() - 1 {
            assert!(numbers[i] <= numbers[i + 1]);
        }
    }

    #[test]
    fn test_random_sequence_custom_order() {
        let mut numbers = Vec::new();
        for _ in 1..1000 {
            numbers.push(rand::random::<i32>());
        }

        sort_by(numbers.as_mut_slice(), &|a, b| b.cmp(a));

        for i in 0..numbers.len() - 1 {
            assert!(numbers[i] >= numbers[i + 1]);
        }
    }
}