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
use std::fmt::Debug; pub fn pivot<T: PartialOrd>(input: &mut [T]) -> usize { let mut p = 0; for i in 1..input.len() { if input[i] < input[p] { input.swap(p + 1, i); input.swap(p, p + 1); p += 1; } } p } pub fn quick_sort<T: PartialOrd + Debug>(input: &mut [T]) { if input.len() <= 1 { return; } let p = pivot(input); let (a, b) = input.split_at_mut(p); quick_sort(a); quick_sort(&mut b[1..]); } pub fn quick_sort_rayon<T: Send + PartialOrd + Debug>(input: &mut [T]) { if input.len() <= 1 { return; } let p = pivot(input); let (a, b) = input.split_at_mut(p); rayon::join(|| quick_sort(a), || quick_sort(&mut b[1..])); } #[cfg(test)] mod tests { use super::*; #[test] fn test_pivot() { let mut v = vec![1, 2, 6, 3, 9, 0]; let p = pivot(&mut v); for x in 0..v.len() { assert_eq!(v[x] < v[p], x < p); } } #[test] fn test_quick_sort() { let mut v = vec![1, 2, 6, 3, 9, 0]; quick_sort(&mut v); assert_eq!(v, vec![0, 1, 2, 3, 6, 9]) } #[test] fn test_quick_sort_rayon() { let mut v = vec![1, 2, 6, 3, 9, 0, 25, 34, 10]; quick_sort_rayon(&mut v); assert_eq!(v, vec![0, 1, 2, 3, 6, 9, 10, 25, 34]) } }