-
Notifications
You must be signed in to change notification settings - Fork 73
/
bucket_sort.rs
54 lines (45 loc) · 1.24 KB
/
bucket_sort.rs
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
use crate::sorting::insertion_sort::InsertionSort;
use crate::sorting::traits::Sorter;
fn bucket_sort<T: Ord + Copy + Into<usize>>(arr: &mut [T]) {
if arr.is_empty() {
return;
}
let max = *arr.iter().max().unwrap();
let len = arr.len();
let mut buckets = vec![vec![]; len + 1];
for x in arr.iter() {
buckets[len * (*x).into() / max.into()].push(*x);
}
for bucket in buckets.iter_mut() {
InsertionSort::sort_inplace(bucket);
}
let mut i = 0;
for bucket in buckets {
for x in bucket {
arr[i] = x;
i += 1;
}
}
}
/// Sort a slice using bucket sort algorithm.
///
/// Time complexity is `O(n + k)` on average, where `n` is the number of elements,
/// `k` is the number of buckets used in process.
///
/// Space complexity is `O(n + k)`, as it sorts not in-place.
pub struct BucketSort;
impl<T> Sorter<T> for BucketSort
where
T: Ord + Copy + Into<usize>,
{
fn sort_inplace(arr: &mut [T]) {
bucket_sort(arr);
}
}
#[cfg(test)]
mod tests {
use crate::sorting::traits::Sorter;
use crate::sorting::BucketSort;
sorting_tests!(BucketSort::sort, bucket_sort);
sorting_tests!(BucketSort::sort_inplace, bucket_sort, inplace);
}