Initial commit

1 files changed, 141 insertions, 0 deletions

diff --git a/kattis-kth-alginda-quicksort/src/radix_sort.rs b/kattis-kth-alginda-quicksort/src/radix_sort.rs
new file mode 100644
index 0000000..e7d4e02
--- /dev/null
+++ b/kattis-kth-alginda-quicksort/src/radix_sort.rs
@@ -0,0 +1,141 @@
+use std::mem;
+
+pub trait RadixFilters: 'static {
+    const FILTERS: &'static [fn(&Self) -> u8];
+}
+
+impl RadixFilters for u32 {
+    const FILTERS: &'static [fn(&Self) -> u8] = &[
+        |x| ((x & 0x000000ff) >> (8 * 0)) as _,
+        |x| ((x & 0x0000ff00) >> (8 * 1)) as _,
+        |x| ((x & 0x00ff0000) >> (8 * 2)) as _,
+        |x| ((x & 0xff000000) >> (8 * 3)) as _,
+    ];
+}
+
+impl RadixFilters for i32 {
+    const FILTERS: &'static [fn(&Self) -> u8] = &[
+        |x| ((x & 0x000000ff) >> (8 * 0)) as _,
+        |x| ((x & 0x0000ff00) >> (8 * 1)) as _,
+        |x| ((x & 0x00ff0000) >> (8 * 2)) as _,
+        |x| (((x & 0xff000000u32 as i32) ^ (1 << 31)) >> (8 * 3)) as _,
+    ];
+}
+
+impl RadixFilters for u64 {
+    const FILTERS: &'static [fn(&Self) -> u8] = &[
+        |x| ((x & 0x00000000000000ff) >> (8 * 0)) as _,
+        |x| ((x & 0x000000000000ff00) >> (8 * 1)) as _,
+        |x| ((x & 0x0000000000ff0000) >> (8 * 2)) as _,
+        |x| ((x & 0x00000000ff000000) >> (8 * 3)) as _,
+        |x| ((x & 0x000000ff00000000) >> (8 * 4)) as _,
+        |x| ((x & 0x0000ff0000000000) >> (8 * 5)) as _,
+        |x| ((x & 0x00ff000000000000) >> (8 * 6)) as _,
+        |x| ((x & 0xff00000000000000) >> (8 * 7)) as _,
+    ];
+}
+
+pub fn radix_sort<T>(xs: Vec<T>) -> Vec<T>
+where
+    T: Default + Copy + Clone + RadixFilters,
+{
+    // The first thing that happens it that these two are swapped so thats why this seems backwards
+    let mut output = xs;
+    let mut input = vec![T::default(); output.len()];
+    for f in T::FILTERS {
+        mem::swap(&mut input, &mut output);
+
+        let mut counts = [0; 256];
+        for x in &input {
+            counts[f(x) as usize] += 1;
+        }
+        let mut sum = 0;
+        for c in &mut counts {
+            sum += *c;
+            *c = sum;
+        }
+        for x in input.iter_mut().rev() {
+            let fx = f(x) as usize;
+            counts[fx] -= 1;
+            output[counts[fx]] = *x;
+        }
+    }
+    output
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn basic_rand() {
+        let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
+        let xs: Vec<u32> = (0..1_000_000).map(|_| r.next_u32()).collect();
+
+        let xs = radix_sort(xs);
+        for w in xs.as_slice().windows(2) {
+            assert!(w[0] <= w[1]);
+        }
+    }
+
+    #[test]
+    fn negatives() {
+        let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
+        let xs: Vec<i32> = (0..1_000_000).map(|_| r.next_u32() as i32).collect();
+
+        let xs = radix_sort(xs);
+        for w in xs.as_slice().windows(2) {
+            assert!(w[0] <= w[1], "{} <= {}", w[0], w[1]);
+        }
+    }
+
+    extern crate test;
+    use rand::RngCore;
+    use test::{black_box, Bencher};
+
+    #[bench]
+    fn std_u32_x1e6(b: &mut Bencher) {
+        let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
+        let xs: Vec<u32> = (0..1_000_000).map(|_| r.next_u32()).collect();
+
+        b.iter(|| {
+            let mut xs = black_box(xs.clone());
+            xs.sort();
+            black_box(xs);
+        });
+    }
+
+    #[bench]
+    fn radix_u32_x1e6(b: &mut Bencher) {
+        let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
+        let xs: Vec<u32> = (0..1_000_000).map(|_| r.next_u32()).collect();
+
+        b.iter(|| {
+            let xs = black_box(xs.clone());
+            black_box(radix_sort(xs));
+        });
+    }
+
+    #[bench]
+    fn std_u64_x1e6(b: &mut Bencher) {
+        let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
+        let xs: Vec<u64> = (0..1_000_000).map(|_| r.next_u64()).collect();
+
+        b.iter(|| {
+            let mut xs = black_box(xs.clone());
+            xs.sort();
+            black_box(xs);
+        });
+    }
+
+    #[bench]
+    fn radix_u64_x1e6(b: &mut Bencher) {
+        let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
+        let xs: Vec<u64> = (0..1_000_000).map(|_| r.next_u64()).collect();
+
+        b.iter(|| {
+            let xs = black_box(xs.clone());
+            black_box(radix_sort(xs));
+        });
+    }
+}