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