From c8e1e71eb526475dd431443345262c2e5a627831 Mon Sep 17 00:00:00 2001
From: Nicholas Noll <nnoll523@gmail.com>
Date: Sat, 23 Oct 2021 11:17:25 -0700
Subject: chore(rename): libn -> base

---
 include/base/macro/qsort.h | 91 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 91 insertions(+)
 create mode 100644 include/base/macro/qsort.h

(limited to 'include/base/macro/qsort.h')

diff --git a/include/base/macro/qsort.h b/include/base/macro/qsort.h
new file mode 100644
index 0000000..6d0acaa
--- /dev/null
+++ b/include/base/macro/qsort.h
@@ -0,0 +1,91 @@
+#pragma once
+
+/* 
+ * Nicholas Noll (2020)
+ * Straight implementation of Sedgewick's median qsort 
+ * #ref: "Implementing Quicksort Programs" (1978)
+ *
+ * @LEN:   name of parameter length
+ * @QLESS: name of function that computes array[i] < array[j]
+ *         should return a boolean
+ * @QSWAP: name of function that swaps array[i] <-> array[j]
+ *         this could swap multiple arrays
+ *
+ * NOTE: This can perform on strided arrays.
+ *       Make sure to use parens liberally to ensure hygeine!
+ */
+
+#define QSORT(LEN, QLESS, QSWAP)                   \
+    int i, j, m, r, l;                             \
+    struct {                                       \
+        int i, j;                                  \
+    } *sp, base[48];                               \
+    sp = base;                                     \
+                                                   \
+    l = 1;                                         \
+    r = LEN-1;                                     \
+                                                   \
+    if (LEN <= 14) goto ENDOUTER;                  \
+OUTERLOOP:                                         \
+    SWAP((l+r)/2, l+1);                            \
+                                                   \
+    if (QLESS(r, l+1)) QSWAP(r, l+1);              \
+    if (QLESS(r, l))   QSWAP(r, l);                \
+    if (QLESS(l, l+1)) QSWAP(l, l+1);              \
+                                                   \
+    i = l+1;                                       \
+    j = r;                                         \
+                                                   \
+INNERLOOP:                                         \
+    do ++i; while(QLESS(i, l));                    \
+    do --j; while(QLESS(l, j));                    \
+    if (j < i) goto ENDINNER;                      \
+    QSWAP(i, j);                                   \
+    goto INNERLOOP;                                \
+                                                   \
+ENDINNER:                                          \
+    QSWAP(l, j);                                   \
+                                                   \
+    if (MAX(j-l, r-i+1) <= 14) {                   \
+        if (sp == base) {                          \
+            goto ENDOUTER;                         \
+        } else {                                   \
+            l = sp[-1].i;                          \
+            r = sp[-1].j;                          \
+            sp--;                                  \
+        }                                          \
+    } else {                                       \
+        if (MIN(j-l, r-i+1) <= 14) {               \
+            if (j-l > r-i+1) {                     \
+                l = l;                             \
+                r = j-1;                           \
+            } else {                               \
+                l = i;                             \
+                r = r;                             \
+            }                                      \
+        } else {                                   \
+            if (j-l > r-i+1) {                     \
+                sp->i = l;                         \
+                sp->j = j-1;                       \
+                sp++;                              \
+                                                   \
+                l = i;                             \
+                r = r;                             \
+            } else {                               \
+                sp->i = i;                         \
+                sp->j = r;                         \
+                sp++;                              \
+                                                   \
+                l = l;                             \
+                r = j-1;                           \
+            }                                      \
+        }                                          \
+    }                                              \
+    goto OUTERLOOP;                                \
+                                                   \
+ENDOUTER:                                          \
+    for (i = 1; i < LEN; i++) {                    \
+        for (j = i; j > 0 && QLESS(j, j-1); j--) { \
+            QSWAP(j, j-1);                         \
+        }                                          \
+    }                                              
-- 
cgit v1.2.1