summaryrefslogtreecommitdiff
path: root/kattis-kth-alginda-quicksort
diff options
context:
space:
mode:
Diffstat (limited to 'kattis-kth-alginda-quicksort')
-rw-r--r--kattis-kth-alginda-quicksort/Cargo.lock85
-rw-r--r--kattis-kth-alginda-quicksort/Cargo.toml12
-rw-r--r--kattis-kth-alginda-quicksort/gen.py11
-rw-r--r--kattis-kth-alginda-quicksort/radix.c146
-rw-r--r--kattis-kth-alginda-quicksort/src/main.rs28
-rw-r--r--kattis-kth-alginda-quicksort/src/radix_sort.rs141
-rwxr-xr-xkattis-kth-alginda-quicksort/test.fish10
7 files changed, 433 insertions, 0 deletions
diff --git a/kattis-kth-alginda-quicksort/Cargo.lock b/kattis-kth-alginda-quicksort/Cargo.lock
new file mode 100644
index 0000000..b3ab7a2
--- /dev/null
+++ b/kattis-kth-alginda-quicksort/Cargo.lock
@@ -0,0 +1,85 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "cfg-if"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+
+[[package]]
+name = "getrandom"
+version = "0.2.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d39cd93900197114fa1fcb7ae84ca742095eed9442088988ae74fa744e930e77"
+dependencies = [
+ "cfg-if",
+ "libc",
+ "wasi",
+]
+
+[[package]]
+name = "kattis-kth-alginda-quicksort"
+version = "0.1.0"
+dependencies = [
+ "rand",
+ "rand_pcg",
+]
+
+[[package]]
+name = "libc"
+version = "0.2.119"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1bf2e165bb3457c8e098ea76f3e3bc9db55f87aa90d52d0e6be741470916aaa4"
+
+[[package]]
+name = "ppv-lite86"
+version = "0.2.16"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "eb9f9e6e233e5c4a35559a617bf40a4ec447db2e84c20b55a6f83167b7e57872"
+
+[[package]]
+name = "rand"
+version = "0.8.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404"
+dependencies = [
+ "libc",
+ "rand_chacha",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_chacha"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88"
+dependencies = [
+ "ppv-lite86",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_core"
+version = "0.6.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d34f1408f55294453790c48b2f1ebbb1c5b4b7563eb1f418bcfcfdbb06ebb4e7"
+dependencies = [
+ "getrandom",
+]
+
+[[package]]
+name = "rand_pcg"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "59cad018caf63deb318e5a4586d99a24424a364f40f1e5778c29aca23f4fc73e"
+dependencies = [
+ "rand_core",
+]
+
+[[package]]
+name = "wasi"
+version = "0.10.2+wasi-snapshot-preview1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "fd6fbd9a79829dd1ad0cc20627bf1ed606756a7f77edff7b66b7064f9cb327c6"
diff --git a/kattis-kth-alginda-quicksort/Cargo.toml b/kattis-kth-alginda-quicksort/Cargo.toml
new file mode 100644
index 0000000..4968225
--- /dev/null
+++ b/kattis-kth-alginda-quicksort/Cargo.toml
@@ -0,0 +1,12 @@
+[package]
+name = "kattis-kth-alginda-quicksort"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dev-dependencies]
+rand = "0.8"
+rand_pcg = "0.3"
+
+[dependencies]
diff --git a/kattis-kth-alginda-quicksort/gen.py b/kattis-kth-alginda-quicksort/gen.py
new file mode 100644
index 0000000..37c4095
--- /dev/null
+++ b/kattis-kth-alginda-quicksort/gen.py
@@ -0,0 +1,11 @@
+from random import randint as r
+from sys import argv
+
+lo = int(argv[1])
+hi = int(argv[2])
+n = int(argv[3])
+
+xs = [r(lo, hi) for _ in range(n)]
+
+print(len(xs), " ")
+print(' \n '.join(str(x) for x in xs))
diff --git a/kattis-kth-alginda-quicksort/radix.c b/kattis-kth-alginda-quicksort/radix.c
new file mode 100644
index 0000000..babc0ec
--- /dev/null
+++ b/kattis-kth-alginda-quicksort/radix.c
@@ -0,0 +1,146 @@
+/* https://kth.kattis.com/problems/kth.alginda.quicksort */
+
+#include <unistd.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdint.h>
+/* #include <immintrin.h> */
+
+// longest int: -2147483648
+#define BUFFER_MAX (12 * 600000)
+char buffer[BUFFER_MAX];
+int xs[600000];
+int tmp[600000];
+
+int *radix_sort(int n) {
+ int *out = xs;
+ int *in = tmp;
+ // we loop an even amount of times so the completely sorted array
+ // will be in xs, not tmp
+ for (int m = 0; m < 32; m += 8) {
+ int *tmp = out;
+ out = in;
+ in = tmp;
+
+ int counts[256] = { 0 };
+ for (int i = 0; i < n; i++)
+ counts[(uint8_t) (in[i] >> m)]++;
+
+ int sum = 0;
+ for (int i = 0; i < 256; i++) {
+ sum += counts[i];
+ counts[i] = sum;
+ }
+ for (int i = n - 1; i >= 0; i--) {
+ uint8_t fx = in[i] >> m;
+ counts[fx]--;
+ out[counts[fx]] = in[i];
+ }
+ }
+}
+
+int main() {
+ /* char *buffer = malloc(BUFFER_MAX); */
+ /* ssize_t len = 0; */
+ /* while (true) { */
+ /* if (len >= BUFFER_MAX) return 1; */
+ /* ssize_t r = read(0, &buffer[len], BUFFER_MAX - len); */
+ /* len += r; */
+ /* if (r == 0) */
+ /* break; */
+ /* } */
+ ssize_t len = read(0, buffer, BUFFER_MAX);
+
+ int curr = 0;
+ int n = 0;
+ while (buffer[curr] != ' ' && buffer[curr] != '\n') {
+ n *= 10;
+ n += buffer[curr] - '0';
+ curr++;
+ }
+ while (buffer[curr] == ' ' || buffer[curr] == '\n') curr++;
+
+ for (int i = 0; i < n; i++) {
+ int x = 0;
+ bool neg = false;
+ if (buffer[curr] == '-') {
+ neg = true;
+ curr++;
+ }
+ while (curr < len && buffer[curr] != ' ' && buffer[curr] != '\n') {
+ x *= 10;
+ x += buffer[curr] - '0';
+ curr++;
+ }
+ while (curr < len && (buffer[curr] == ' ' || buffer[curr] == '\n')) curr++;
+
+ if (neg) x = -x;
+ xs[i] = x ^ (1 << 31);
+ }
+
+ radix_sort(n);
+
+ len = 0;
+ for (int i = 0; i < n; i++, len += 12) {
+ long x = xs[i] ^ (1 << 31);
+ bool neg = false;
+ if (x < 0) {
+ neg = true;
+ x = -x;
+ }
+ int j = 11;
+ buffer[len + j--] = '\n';
+ do {
+ buffer[len + j--] = (x % 10) + '0';
+ x /= 10;
+ } while (x > 0);
+ if (neg) buffer[len + j--] = '-';
+ while (j >= 0) buffer[len + j--] = ' ';
+ }
+
+ /*
+ len = 0;
+
+ __m256i highestbit = _mm256_set1_epi32(1 << 32);
+ __m256i zero = _mm256_set1_epi32(0);
+ __m256i lens = _mm256_set_epi32(0 * 12,
+ 1 * 12,
+ 2 * 12,
+ 3 * 12,
+ 4 * 12,
+ 5 * 12,
+ 6 * 12,
+ 7 * 12);
+ __m256i lenoffset = _mm256_set1_epi(8 * 12);
+
+ for (int i = 0; i < n; i += 8) {
+ // long x = xs[i] ^ (1 << 31);
+ __m256i xx = _mm256_load_si256(&xs[i]);
+ xx = _mm256_xor_si256(xx, highestbit);
+ // bool neg = false;
+ // if (x < 0) {
+ // neg = true;
+ // x = -x;
+ // }
+ __m256i negs = _mm256_cmpgt(zero, xx);
+ xx = _mm256_abs_epi64(xx);
+ // todo...
+ int j = 11;
+ buffer[len + j--] = '\n';
+ do {
+ buffer[len + j--] = (x % 10) + '0';
+ x /= 10;
+ } while (x > 0);
+ if (neg) buffer[len + j--] = '-';
+ while (j >= 0) buffer[len + j--] = ' ';
+
+ // len += 8 * 12
+ lens = _mm256_add_epi32(lens, lenoffset);
+ }
+ */
+ /* ssize_t c = 0; */
+ /* while (c < len) c += write(1, &buffer[c], len - c); */
+ write(1, buffer, len);
+}
diff --git a/kattis-kth-alginda-quicksort/src/main.rs b/kattis-kth-alginda-quicksort/src/main.rs
new file mode 100644
index 0000000..67646b3
--- /dev/null
+++ b/kattis-kth-alginda-quicksort/src/main.rs
@@ -0,0 +1,28 @@
+// https://kth.kattis.com/problems/kth.alginda.quicksort
+
+#![feature(test)]
+
+use std::fmt::Write;
+use std::io::{stdin, Read};
+
+mod radix_sort;
+
+use radix_sort::radix_sort;
+
+fn main() {
+ let mut buffer = String::new();
+ stdin().lock().read_to_string(&mut buffer).unwrap();
+ let xs: Vec<i32> = buffer
+ .split_ascii_whitespace()
+ .skip(1)
+ .map(|x| x.parse().unwrap())
+ .collect();
+
+ let xs = radix_sort(xs);
+
+ buffer.clear();
+ for x in xs {
+ writeln!(buffer, "{}", x).unwrap();
+ }
+ print!("{}", buffer);
+}
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));
+ });
+ }
+}
diff --git a/kattis-kth-alginda-quicksort/test.fish b/kattis-kth-alginda-quicksort/test.fish
new file mode 100755
index 0000000..6aaf60c
--- /dev/null
+++ b/kattis-kth-alginda-quicksort/test.fish
@@ -0,0 +1,10 @@
+#!/bin/fish
+
+echo hej > out_c
+echo hej > out_r
+
+while diff out_c out_r
+ python gen.py -2147483648 2147483647 600000 > max
+ time ./radix < max > out_r
+ time ~/.cache/target/release/kattis-kth-alginda-quicksort < max > out_c
+end
generated by cgit v1.2.3 (git 2.25.1) at 2025-09-10 18:22:33 +0000