quick_sort/
lib.rs

1//! A standard in-place quick sort using a median of
2//! first, middle and last element in each slice for the pivot.
3
4
5/// # Example
6///
7/// ```
8/// let mut numbers = vec![12, 2, -9, -45, 0, 67];
9/// quick_sort::sort(numbers.as_mut_slice());
10/// ```
11
12use std::cmp::Ordering;
13
14pub fn sort<T>(arr: &mut [T])
15    where T: std::cmp::PartialEq + Ord
16{
17    qsort(arr, find_pivot, &|a, b| a.cmp(b))
18}
19
20
21/// # Example
22///
23/// ```
24/// let mut numbers = vec![12, 2, -9, -45, 0, 67];
25/// quick_sort::sort_by(numbers.as_mut_slice(), &|a, b| b.cmp(a));
26/// ```
27pub fn sort_by<T, F>(arr: &mut [T], compare: &F)
28    where T: std::cmp::PartialOrd,
29          F: Fn(&T, &T) -> Ordering
30{
31    qsort(arr, find_pivot, compare);
32}
33
34fn qsort<T, F>(arr: &mut [T], pivot: fn(&[T], &F) -> usize, compare: &F)
35    where T: std::cmp::PartialOrd,
36          F: Fn(&T, &T) -> Ordering
37{
38    let len = arr.len();
39    if len <= 1 {
40        return;
41    }
42
43    let p = pivot(arr, compare);
44    let p = partition(arr, p, compare);
45    if p > len / 2 {
46        qsort(&mut arr[p + 1..len], pivot, compare);
47        qsort(&mut arr[0..p], pivot, compare);
48    } else {
49        qsort(&mut arr[0..p], pivot, compare);
50        qsort(&mut arr[p + 1..len], pivot, compare);
51    }
52}
53
54fn find_pivot<T, F>(arr: &[T], compare: &F) -> usize
55    where T: std::cmp::PartialOrd,
56          F: Fn(&T, &T) -> Ordering
57{
58    let (l, r) = (0, arr.len() - 1);
59    let m = l + ((r - 1) / 2);
60    let (left, middle, right) = (&arr[l], &arr[m], &arr[r]);
61    if (compare(middle, left) != Ordering::Less) && (compare(middle, right) != Ordering::Greater) {
62        m
63    } else if (compare(left, middle) != Ordering::Less) &&
64              (compare(left, right) != Ordering::Greater) {
65        l
66    } else {
67        r
68    }
69}
70
71
72fn partition<T, F>(arr: &mut [T], p: usize, compare: &F) -> usize
73    where T: std::cmp::PartialOrd,
74          F: Fn(&T, &T) -> Ordering
75{
76    if arr.len() <= 1 {
77        return p;
78    }
79
80    let last = arr.len() - 1;
81    let mut next_pivot = 0;
82    arr.swap(last, p);
83    for i in 0..last {
84        if compare(&arr[i], &arr[last]) == Ordering::Less {
85            arr.swap(i, next_pivot);
86            next_pivot += 1;
87        }
88    }
89
90    arr.swap(next_pivot, last);
91    next_pivot
92}
93
94#[cfg(test)]
95mod test {
96    extern crate rand;
97    use super::sort;
98    use super::sort_by;
99
100    #[test]
101    fn test_random_sequece_default_order() {
102        let mut numbers = Vec::new();
103        for _ in 1..1000 {
104            numbers.push(rand::random::<i32>());
105        }
106
107        sort(numbers.as_mut_slice());
108
109        for i in 0..numbers.len() - 1 {
110            assert!(numbers[i] <= numbers[i + 1]);
111        }
112    }
113
114    #[test]
115    fn test_random_sequence_custom_order() {
116        let mut numbers = Vec::new();
117        for _ in 1..1000 {
118            numbers.push(rand::random::<i32>());
119        }
120
121        sort_by(numbers.as_mut_slice(), &|a, b| b.cmp(a));
122
123        for i in 0..numbers.len() - 1 {
124            assert!(numbers[i] >= numbers[i + 1]);
125        }
126    }
127}
quick_sort/lib.rs

quick_sort/
lib.rs
