Algod/sorting/
radix_sort.rs

1/// Sorts the elements of `arr` in-place using radix sort.
2///
3/// Time complexity is `O((n + b) * logb(k))`, where `n` is the number of elements,
4/// `b` is the base (the radix), and `k` is the largest element.
5/// When `n` and `b` are roughly the same maginitude, this algorithm runs in linear time.
6///
7/// Space complexity is `O(n + b)`.
8pub fn radix_sort(arr: &mut [u64]) {
9    let max: usize = match arr.iter().max() {
10        Some(&x) => x as usize,
11        None => return,
12    };
13    // Make radix a power of 2 close to arr.len() for optimal runtime
14    let radix = arr.len().next_power_of_two();
15    // Counting sort by each digit from least to most significant
16    let mut place = 1;
17    while place <= max {
18        let digit_of = |x| x as usize / place % radix;
19        // Count digit occurrences
20        let mut counter = vec![0; radix];
21        for &x in arr.iter() {
22            counter[digit_of(x)] += 1;
23        }
24        // Compute last index of each digit
25        for i in 1..radix {
26            counter[i] += counter[i - 1];
27        }
28        // Write elements to their new indices
29        for &x in arr.to_owned().iter().rev() {
30            counter[digit_of(x)] -= 1;
31            arr[counter[digit_of(x)]] = x;
32        }
33        place *= radix;
34    }
35}
36
37#[cfg(test)]
38mod tests {
39    use super::super::is_sorted;
40    use super::radix_sort;
41
42    #[test]
43    fn empty() {
44        let mut a: [u64; 0] = [];
45        radix_sort(&mut a);
46        assert!(is_sorted(&a));
47    }
48
49    #[test]
50    fn descending() {
51        let mut v = vec![201, 127, 64, 37, 24, 4, 1];
52        radix_sort(&mut v);
53        assert!(is_sorted(&v));
54    }
55
56    #[test]
57    fn ascending() {
58        let mut v = vec![1, 4, 24, 37, 64, 127, 201];
59        radix_sort(&mut v);
60        assert!(is_sorted(&v));
61    }
62}
Algod/sorting/radix_sort.rs

Algod/sorting/
radix_sort.rs
