1pub trait BucketSort {
2 fn bucket_sort(&mut self);
3}
4
5impl BucketSort for [usize] {
6 fn bucket_sort(&mut self) {
7 if self.is_empty() {
8 return;
9 }
10
11 let m = *self.iter().max().unwrap();
12 let mut count = vec![0; m + 1];
13 for &ai in &*self {
14 count[ai] += 1;
15 }
16 let mut i = 0;
17 for j in 0..=m {
18 for _ in 0..count[j] {
19 self[i] = j;
20 i += 1;
21 }
22 }
23 }
24}
25
26#[test]
27fn sanity_check() {
28 let mut empty = vec![];
29 empty.bucket_sort();
30 assert_eq!(empty, []);
31
32 let mut a = vec![3, 1, 4, 1, 5, 9, 2];
33 a.bucket_sort();
34 assert_eq!(a, [1, 1, 2, 3, 4, 5, 9]);
35}