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]);
        }
    }
}