1 files changed, 109 insertions, 0 deletions
diff --git a/kattis-kth/alginda-quicksort/radix.jl b/kattis-kth/alginda-quicksort/radix.jl
new file mode 100644
index 0000000..536ad90
--- /dev/null
+++ b/kattis-kth/alginda-quicksort/radix.jl
@@ -0,0 +1,109 @@
+# https://kth.kattis.com/problems/kth.alginda.quicksort
+
+using OffsetArrays
+
+function radixsort(xs::AbstractVector{UInt32})
+    xs, ys = similar(xs), xs
+    counts = OffsetArray(Vector{UInt32}(undef, 256), 0:255)
+    for m = 0:8:32
+        xs, ys = ys, xs
+
+        fill!(counts, 0)
+        for x = xs
+            counts[x >> m & 0xff] += 1
+        end
+
+        sum = 0
+        for i = firstindex(counts):lastindex(counts)
+            sum += counts[i]
+            counts[i] = sum
+        end
+
+        for i = length(xs):-1:1
+            fx = xs[i] >> m & 0xff
+            ys[counts[fx]] = xs[i]
+            counts[fx] -= 1
+        end
+    end
+    ys
+end
+
+function main()
+    @time xs = map(x -> UInt32(1 << 31) ⊻ parse(Int32, x), readline() |> split)[2:end]
+    @time xs = radixsort(xs)
+    @time for x in xs
+        println(Int32(UInt32(1 << 31) ⊻ x))
+    end
+end
+
+main()
+@time main()
+
+#=
+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); */
+}
+=#