1 files changed, 72 insertions, 0 deletions
diff --git a/kattis-kth/alginda-quicksort/src/main.rs b/kattis-kth/alginda-quicksort/src/main.rs
new file mode 100644
index 0000000..afb23f7
--- /dev/null
+++ b/kattis-kth/alginda-quicksort/src/main.rs
@@ -0,0 +1,72 @@
+// https://kth.kattis.com/problems/kth.alginda.quicksort
+
+#![feature(test)]
+
+use std::io::{stdin, stdout, Read, Write};
+
+mod radix_sort;
+use radix_sort::radix_sort;
+
+fn main() {
+    let mut buffer = String::new();
+    stdin().lock().read_to_string(&mut buffer).unwrap();
+    let mut p = buffer.bytes();
+    let mut n = 0;
+    while let Some(b) = p.next() {
+        if b == b' ' {
+            break;
+        }
+        n *= 10;
+        n += (b - b'0') as usize;
+    }
+    let mut xs = vec![0; n];
+    for i in 0..n {
+        let mut neg = false;
+        let mut x = 0i32;
+        while let Some(b) = p.next() {
+            match b {
+                b' ' | b'\n' => break,
+                b'-' => neg = true,
+                b => {
+                    x *= 10;
+                    x += (b - b'0') as i32;
+                }
+            }
+        }
+        if neg {
+            x = -x;
+        }
+        xs[i] = x;
+    }
+
+    radix_sort(&mut xs);
+
+    let mut p = buffer.len() - 1;
+    let b = unsafe { buffer.as_mut_vec() };
+    b[p] = b'\n';
+    p -= 1;
+    for i in (0..n).rev() {
+        let x = xs[i];
+        let neg = x < 0;
+        let mut x = if neg { (-x) as u32 } else { x as u32 };
+        loop {
+            b[p] = (x % 10) as u8 + b'0';
+            p -= 1;
+            x /= 10;
+            if x == 0 {
+                break;
+            }
+        }
+        if neg {
+            b[p] = b'-';
+            p -= 1;
+        }
+        if i > 0 {
+            b[p] = b'\n';
+            p -= 1;
+        }
+    }
+    p += 1;
+
+    stdout().lock().write(&b[p..]).unwrap();
+}