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.py10
-rw-r--r--kattis-kth-alginda-quicksort/radix.c108
-rw-r--r--kattis-kth-alginda-quicksort/radix.go99
-rw-r--r--kattis-kth-alginda-quicksort/radix64.c95
-rw-r--r--kattis-kth-alginda-quicksort/src/main.rs72
-rw-r--r--kattis-kth-alginda-quicksort/src/radix_sort.rs151
-rwxr-xr-xkattis-kth-alginda-quicksort/test11
9 files changed, 0 insertions, 643 deletions
diff --git a/kattis-kth-alginda-quicksort/Cargo.lock b/kattis-kth-alginda-quicksort/Cargo.lock
deleted file mode 100644
index b3ab7a2..0000000
--- a/kattis-kth-alginda-quicksort/Cargo.lock
+++ /dev/null
@@ -1,85 +0,0 @@
-# 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
deleted file mode 100644
index 4968225..0000000
--- a/kattis-kth-alginda-quicksort/Cargo.toml
+++ /dev/null
@@ -1,12 +0,0 @@
-[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
deleted file mode 100644
index 2e5067b..0000000
--- a/kattis-kth-alginda-quicksort/gen.py
+++ /dev/null
@@ -1,10 +0,0 @@
-from random import randint as r
-from sys import argv
-
-lo = int(argv[1])
-hi = int(argv[2])
-n = int(argv[3]) if len(argv) > 3 else r(1, 600000)
-
-xs = [r(lo, hi) for _ in range(n)]
-
-print(len(xs), *(str(x) for x in xs))
diff --git a/kattis-kth-alginda-quicksort/radix.c b/kattis-kth-alginda-quicksort/radix.c
deleted file mode 100644
index 93bd111..0000000
--- a/kattis-kth-alginda-quicksort/radix.c
+++ /dev/null
@@ -1,108 +0,0 @@
-/* https://kth.kattis.com/problems/kth.alginda.quicksort */
-
-#include <stdbool.h>
-#include <stdlib.h>
-#include <string.h>
-#include <stdio.h>
-#include <stdint.h>
-#include <unistd.h>
-
-// longest int: -2147483648
-#define BUFFER_MAX (12 * 600000)
-char buffer[BUFFER_MAX];
-int xs[600000];
-int tmp[600000];
-
-void radix_sort(int n) {
- int *out = xs;
- int *in = tmp;
- // we loop an even amount of times so the final sorted array will be in xs.
- // if we looped an odd amount of times this would not be the case
- 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);
-
- char *p = buffer;
- char *end = &buffer[len];
- int n = 0;
- while (*p != ' ') {
- n *= 10;
- n += *p - '0';
- p++;
- }
- while (*p == ' ' || *p == '\n') p++;
-
- // 18 ms
- for (int i = 0; i < n; i++) {
- int x = 0;
- bool neg = false;
- if (*p == '-') {
- neg = true;
- p++;
- }
- while (p < end && *p != ' ' && *p != '\n') {
- x *= 10;
- x += *p - '0';
- p++;
- }
- while (p < end && (*p == ' ' || *p == '\n')) p++;
-
- if (neg) x = -x;
- xs[i] = x ^ (1 << 31);
- }
-
- // 10 ms
- radix_sort(n);
-
- // 17 ms
- p = &buffer[BUFFER_MAX - 1];
- char *last = p;
- *p-- = '\n';
- for (int i = n - 1; i >= 0; i--) {
- int signedx = xs[i] ^ (1 << 31);
- bool neg = signedx < 0;
- uint32_t x;
- if (neg) x = -signedx;
- else x = signedx;
- do {
- *p-- = (x % 10) + '0';
- x /= 10;
- } while (x > 0);
- if (neg) *p-- = '-';
- if (i > 0) *p-- = '\n';
- }
- write(1, p + 1, last - p);
-
- /* ssize_t c = 0; */
- /* while (c < len) c += write(1, &buffer[c], len - c); */
-}
diff --git a/kattis-kth-alginda-quicksort/radix.go b/kattis-kth-alginda-quicksort/radix.go
deleted file mode 100644
index d847547..0000000
--- a/kattis-kth-alginda-quicksort/radix.go
+++ /dev/null
@@ -1,99 +0,0 @@
-package main
-
-import (
- "os"
-)
-
-var xs [600_000]int32
-var ys [600_000]int32
-
-func radixSort(n int) {
- ys, xs := xs[:n], ys[:n]
- for m := 0; m < 32; m += 8 {
- xs, ys = ys, xs
-
- var counts [256]int32
- for _, x := range xs {
- counts[x>>m&0xff]++
- }
-
- for i := 1; i < len(counts); i++ {
- counts[i] += counts[i-1]
- }
-
- for i := len(xs) - 1; i >= 0; i-- {
- counts[xs[i]>>m&0xff]--
- ys[counts[xs[i]>>m&0xff]] = xs[i]
- }
- }
-}
-
-var buf [600_000 * 12]byte
-
-func main() {
- n, _ := os.Stdin.Read(buf[:])
- b := buf[:n]
- i := 0
-
- count := 0
- for ; b[i] != ' '; i++ {
- count = count*10 + int(b[i]-'0')
- }
- i++ // skip space
-
- for j := 0; j < count; j++ {
- x := int32(0)
- neg := false
- if b[i] == '-' {
- neg = true
- i++
- }
- for ; '0' <= b[i] && b[i] <= '9'; i++ {
- x = x*10 + int32(b[i]-'0')
- }
- i++ // skip space
-
- if neg {
- x = -x
- }
- var bit int32 = 1
- xs[j] = x ^ bit<<31
- }
-
- radixSort(count)
-
- b = buf[:]
- i = 600_000*12 - 1
- b[i] = '\n'
- i--
- for j := count - 1; j >= 0; j-- {
- var bit int32 = 1
- sx := xs[j] ^ bit<<31
- neg := sx < 0
- var x uint32
- if neg {
- x = uint32(-sx)
- } else {
- x = uint32(sx)
- }
- if x == 0 {
- b[i] = '0'
- i--
- }
- for x > 0 {
- b[i] = '0' + byte(x%10)
- x /= 10
- i--
- }
- if neg {
- b[i] = '-'
- i--
- }
- if j > 0 {
- b[i] = '\n'
- i--
- }
- }
-
- os.Stdout.Write(b[i+1:])
-}
diff --git a/kattis-kth-alginda-quicksort/radix64.c b/kattis-kth-alginda-quicksort/radix64.c
deleted file mode 100644
index 54b0155..0000000
--- a/kattis-kth-alginda-quicksort/radix64.c
+++ /dev/null
@@ -1,95 +0,0 @@
-/* https://kth.kattis.com/problems/kth.alginda.quicksort */
-
-#include <stdbool.h>
-#include <stdlib.h>
-#include <string.h>
-#include <stdio.h>
-#include <stdint.h>
-#include <unistd.h>
-
-// longest int: -2147483648
-#define BUFFER_MAX (12 * 600000)
-char buffer[BUFFER_MAX];
-long xs[600000];
-long tmp[600000];
-
-void radix_sort(int n) {
- long *out = xs;
- long *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 < 40; m += 8) {
- long *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() {
- ssize_t len = read(0, buffer, BUFFER_MAX);
-
- char *p = buffer;
- int n = 0;
- while (*p != ' ') {
- n *= 10;
- n += *p - '0';
- p++;
- }
-
- p = &buffer[len - 1];
- for (int i = n - 1; i >= 0; i--) {
- while (*p == ' ' || *p == '\n') p--;
-
- long x = 0;
-
- bool c = true;
- if (c) x += (long)(*p-- - '0') << 0; if (*p == ' ' || *p == '\n') c = false;
- if (c) x += (long)(*p-- - '0') << 4; if (*p == ' ' || *p == '\n') c = false;
- if (c) x += (long)(*p-- - '0') << 8; if (*p == ' ' || *p == '\n') c = false;
- if (c) x += (long)(*p-- - '0') << 12; if (*p == ' ' || *p == '\n') c = false;
- if (c) x += (long)(*p-- - '0') << 16; if (*p == ' ' || *p == '\n') c = false;
- if (c) x += (long)(*p-- - '0') << 20; if (*p == ' ' || *p == '\n') c = false;
- if (c) x += (long)(*p-- - '0') << 24; if (*p == ' ' || *p == '\n') c = false;
- if (c) x += (long)(*p-- - '0') << 28; if (*p == ' ' || *p == '\n') c = false;
- if (c) x += (long)(*p-- - '0') << 32; if (*p == ' ' || *p == '\n') c = false;
- if (c) x += (long)(*p-- - '0') << 36;
-
- xs[i] = x;
- }
-
- radix_sort(n);
-
- p = &buffer[BUFFER_MAX - 1];
- char *last = p;
- *p-- = '\n';
- for (int i = n - 1; i >= 0; i--) {
- long x = xs[i];
- *p-- = (x & 0xf) + '0'; x >>= 4;
- if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
- if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
- if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
- if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
- if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
- if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
- if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
- if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
- if (x) *p-- = (x & 0xf) + '0'; x >>= 4;
- if (i > 0) *p-- = '\n';
- }
- write(1, p + 1, last - p);
-}
diff --git a/kattis-kth-alginda-quicksort/src/main.rs b/kattis-kth-alginda-quicksort/src/main.rs
deleted file mode 100644
index afb23f7..0000000
--- a/kattis-kth-alginda-quicksort/src/main.rs
+++ /dev/null
@@ -1,72 +0,0 @@
-// 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();
-}
diff --git a/kattis-kth-alginda-quicksort/src/radix_sort.rs b/kattis-kth-alginda-quicksort/src/radix_sort.rs
deleted file mode 100644
index 2f8d32a..0000000
--- a/kattis-kth-alginda-quicksort/src/radix_sort.rs
+++ /dev/null
@@ -1,151 +0,0 @@
-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_with<T>(xs: &mut [T], temp: &mut [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 = temp;
- debug_assert!(T::FILTERS.len() % 2 == 0);
- for f in T::FILTERS {
- mem::swap(&mut input, &mut output);
-
- let mut counts = [0; 256];
- for x in input.iter() {
- 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;
- }
- }
-}
-
-pub fn radix_sort<T>(xs: &mut [T])
-where
- T: Default + Copy + Clone + RadixFilters,
-{
- let n = xs.len();
- radix_sort_with(xs, vec![Default::default(); n].as_mut_slice());
-}
-
-#[cfg(test)]
-mod tests {
- use super::*;
-
- #[test]
- fn basic_rand() {
- let mut r = rand_pcg::Pcg32::new(0xcafef00dd15ea5e5, 0xa02bdbf7bb3c0a7);
- let mut xs: Vec<u32> = (0..1_000_000).map(|_| r.next_u32()).collect();
-
- radix_sort(&mut 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 mut xs: Vec<i32> = (0..1_000_000).map(|_| r.next_u32() as i32).collect();
-
- radix_sort(&mut 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 mut xs = black_box(xs.clone());
- radix_sort(&mut xs);
- black_box(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 mut xs = black_box(xs.clone());
- radix_sort(&mut xs);
- black_box(xs);
- });
- }
-}
diff --git a/kattis-kth-alginda-quicksort/test b/kattis-kth-alginda-quicksort/test
deleted file mode 100755
index 01b0ae7..0000000
--- a/kattis-kth-alginda-quicksort/test
+++ /dev/null
@@ -1,11 +0,0 @@
-#!/bin/sh
-
-echo hej > out_1
-echo hej > out_2
-
-while diff out_1 out_2; do
- echo -n .
- python gen.py -2147483648 2147483647 > max
- "$1" < max > out_1
- "$2" < max > out_2
-done
generated by cgit v1.2.3 (git 2.25.1) at 2025-09-10 21:14:54 +0000