-
Notifications
You must be signed in to change notification settings - Fork 74
/
radix_sort.rs
64 lines (58 loc) · 1.77 KB
/
radix_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
55
56
57
58
59
60
61
62
63
64
use crate::sorting::traits::Sorter;
fn radix_sort<T>(arr: &mut [T])
where
T: Ord + Copy + From<usize> + Into<usize>,
{
if arr.len() <= 1 {
return;
}
let max: usize = match arr.iter().max() {
Some(&x) => x.into(),
None => return,
};
// Make radix a power of 2 close to arr.len() for optimal runtime
let radix = arr.len().next_power_of_two();
// Counting sort by each digit from least to most significant
let mut place: usize = 1;
while place <= max {
let digit_of = |x: T| x.into() / place % radix;
// Count digit occurrences
let mut counter = vec![0; radix];
for &x in arr.iter() {
counter[digit_of(x)] += 1;
}
// Compute last index of each digit
for i in 1..radix {
counter[i] += counter[i - 1];
}
// Write elements to their new indices
for &x in arr.to_owned().iter().rev() {
counter[digit_of(x)] -= 1;
arr[counter[digit_of(x)]] = x;
}
place *= radix;
}
}
/// Sorts the elements of `arr` in-place using radix sort.
///
/// Time complexity is `O((n + b) * logb(k))`, where `n` is the number of elements,
/// `b` is the base (the radix), and `k` is the largest element.
/// When `n` and `b` are roughly the same maginitude, this algorithm runs in linear time.
///
/// Space complexity is `O(n + b)`.
pub struct RadixSort;
impl<T> Sorter<T> for RadixSort
where
T: Ord + Copy + From<usize> + Into<usize>,
{
fn sort_inplace(arr: &mut [T]) {
radix_sort(arr);
}
}
#[cfg(test)]
mod tests {
use crate::sorting::traits::Sorter;
use crate::sorting::RadixSort;
sorting_tests!(RadixSort::sort, radix_sort);
sorting_tests!(RadixSort::sort_inplace, radix_sort, inplace);
}