From d5473756b304ebda9eeee6592e4555d15c910ee2 Mon Sep 17 00:00:00 2001
From: mathiasmagnusson <mathiasmagnussons@gmail.com>
Date: Sun, 27 Feb 2022 17:41:23 +0100
Subject: Improve quicksort

---
 kattis-kth-alginda-quicksort/radix.c | 99 +++++++++++-------------------------
 1 file changed, 29 insertions(+), 70 deletions(-)

(limited to 'kattis-kth-alginda-quicksort/radix.c')

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);
 }
-- 
cgit v1.2.3