1 // This is a buggy quick sort implementation, QuickCheck will find the bug for
2 // you.
3
4 use quickcheck::quickcheck;
5
smaller_than<T: Clone + Ord>(xs: &[T], pivot: &T) -> Vec<T>6 fn smaller_than<T: Clone + Ord>(xs: &[T], pivot: &T) -> Vec<T> {
7 xs.iter().filter(|&x| *x < *pivot).map(|x| x.clone()).collect()
8 }
9
larger_than<T: Clone + Ord>(xs: &[T], pivot: &T) -> Vec<T>10 fn larger_than<T: Clone + Ord>(xs: &[T], pivot: &T) -> Vec<T> {
11 xs.iter().filter(|&x| *x > *pivot).map(|x| x.clone()).collect()
12 }
13
sortk<T: Clone + Ord>(x: &T, xs: &[T]) -> Vec<T>14 fn sortk<T: Clone + Ord>(x: &T, xs: &[T]) -> Vec<T> {
15 let mut result: Vec<T> = sort(&*smaller_than(xs, x));
16 let last_part = sort(&*larger_than(xs, x));
17 result.push(x.clone());
18 result.extend(last_part.iter().map(|x| x.clone()));
19 result
20 }
21
sort<T: Clone + Ord>(list: &[T]) -> Vec<T>22 fn sort<T: Clone + Ord>(list: &[T]) -> Vec<T> {
23 if list.is_empty() {
24 vec![]
25 } else {
26 sortk(&list[0], &list[1..])
27 }
28 }
29
main()30 fn main() {
31 fn is_sorted(xs: Vec<isize>) -> bool {
32 for win in xs.windows(2) {
33 if win[0] > win[1] {
34 return false;
35 }
36 }
37 true
38 }
39
40 fn keeps_length(xs: Vec<isize>) -> bool {
41 xs.len() == sort(&*xs).len()
42 }
43 quickcheck(keeps_length as fn(Vec<isize>) -> bool);
44
45 quickcheck(is_sorted as fn(Vec<isize>) -> bool)
46 }
47