Improve quicksort

2 files changed, 129 insertions, 70 deletions

diff --git a/kattis-kth-alginda-quicksort/radix.c b/kattis-kth-alginda-quicksort/radix.c
index babc0ec..b297d6f 100644
--- a/kattis-kth-alginda-quicksort/radix.c
+++ b/kattis-kth-alginda-quicksort/radix.c
@@ -1,12 +1,11 @@
 /* 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> */
+#include <unistd.h>
 
 // longest int: -2147483648
 #define BUFFER_MAX (12 * 600000)
@@ -14,11 +13,11 @@ char buffer[BUFFER_MAX];
 int xs[600000];
 int tmp[600000];
 
-int *radix_sort(int n) {
+void 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
+    // 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;
@@ -53,28 +52,29 @@ int main() {
     /* } */
     ssize_t len = read(0, buffer, BUFFER_MAX);
 
-    int curr = 0;
+    char *p = buffer;
+    char *end = &buffer[len];
     int n = 0;
-    while (buffer[curr] != ' ' && buffer[curr] != '\n') {
+    while (*p != ' ' && *p != '\n') {
         n *= 10;
-        n += buffer[curr] - '0';
-        curr++;
+        n += *p - '0';
+        p++;
     }
-    while (buffer[curr] == ' ' || buffer[curr] == '\n') curr++;
+    while (*p == ' ' || *p == '\n') p++;
 
     for (int i = 0; i < n; i++) {
         int x = 0;
         bool neg = false;
-        if (buffer[curr] == '-') {
+        if (*p == '-') {
             neg = true;
-            curr++;
+            p++;
         }
-        while (curr < len && buffer[curr] != ' ' && buffer[curr] != '\n') {
+        while (p < end && *p != ' ' && *p != '\n') {
             x *= 10;
-            x += buffer[curr] - '0';
-            curr++;
+            x += *p - '0';
+            p++;
         }
-        while (curr < len && (buffer[curr] == ' ' || buffer[curr] == '\n')) curr++;
+        while (p < end && (*p == ' ' || *p == '\n')) p++;
 
         if (neg) x = -x;
         xs[i] = x ^ (1 << 31);
@@ -82,65 +82,24 @@ int main() {
 
     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';
+    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 {
-            buffer[len + j--] = (x % 10) + '0';
+            *p-- = (x % 10) + '0';
             x /= 10;
         } while (x > 0);
-        if (neg) buffer[len + j--] = '-';
-        while (j >= 0) buffer[len + j--] = ' ';
+        if (neg) *p-- = '-';
+        if (i > 0) *p-- = '\n';
     }
+    write(1, p + 1, last - p);
 
-    /*
-    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/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);
+}