Improve quicksort

1 files changed, 100 insertions, 0 deletions

diff --git a/kattis-kth-alginda-quicksort/radix64.c b/kattis-kth-alginda-quicksort/radix64.c
new file mode 100644
index 0000000..4113a94
--- /dev/null
+++ b/kattis-kth-alginda-quicksort/radix64.c
@@ -0,0 +1,100 @@
+/* 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 < 44; 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 != ' ' && *p != '\n') {
+        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 == '-') c = false;
+        if (c) x += (long)(*p-- - '0') << 4;  if (*p == ' ' || *p == '-') c = false;
+        if (c) x += (long)(*p-- - '0') << 8;  if (*p == ' ' || *p == '-') c = false;
+        if (c) x += (long)(*p-- - '0') << 12; if (*p == ' ' || *p == '-') c = false;
+        if (c) x += (long)(*p-- - '0') << 16; if (*p == ' ' || *p == '-') c = false;
+        if (c) x += (long)(*p-- - '0') << 20; if (*p == ' ' || *p == '-') c = false;
+        if (c) x += (long)(*p-- - '0') << 24; if (*p == ' ' || *p == '-') c = false;
+        if (c) x += (long)(*p-- - '0') << 28; if (*p == ' ' || *p == '-') c = false;
+        if (c) x += (long)(*p-- - '0') << 32; if (*p == ' ' || *p == '-') c = false;
+        if (c) x += (long)(*p-- - '0') << 36;
+
+        if (*p == '-') p--;
+        else x |= 1l << 40;
+
+        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];
+        bool neg = x >> 40 == 0;
+        x &= ~(1l << 40);
+        *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 (neg) *p-- = '-';
+        if (i > 0) *p-- = '\n';
+    }
+    write(1, p + 1, last - p);
+}