From 3d38446f71e16735b2525f37dd1eb87d91c0e895 Mon Sep 17 00:00:00 2001
From: Jakob Kaivo <jkk@ung.org>
Date: Sat, 15 Aug 2020 11:26:40 -0400
Subject: first draft of qsort()

---
 src/stdlib/_qsort.h | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)
 create mode 100644 src/stdlib/_qsort.h

(limited to 'src/stdlib/_qsort.h')

diff --git a/src/stdlib/_qsort.h b/src/stdlib/_qsort.h
new file mode 100644
index 00000000..298e28a1
--- /dev/null
+++ b/src/stdlib/_qsort.h
@@ -0,0 +1,39 @@
+#include <stdlib.h>
+#include <string.h>
+
+struct __qs {
+	char *base;
+	size_t size;
+	int (*compar)(const void *, const void *);
+	char buf[64];
+	char *swap;
+};
+
+static void __swap(struct __qs *a, size_t i, size_t j)
+{
+	memcpy(a->swap, a->base + (a->size * i), a->size);
+	memcpy(a->base + (a->size * i), a->base + (a->size * j), a->size);
+	memcpy(a->base + (a->size * j), a->swap, a->size);
+}
+
+static size_t __partition(struct __qs *a, size_t lo, size_t hi)
+{
+	size_t i = lo, j = 0;
+	for (j = lo; j < hi; j++) {
+		if (a->compar(a->base + (a->size * j), a->base + (a->size * hi)) < 0) {
+			__swap(a, i, j);
+			i++;
+		}
+	}
+	__swap(a, i, hi);
+	return i;
+}
+
+static void __qsort(struct __qs *a, size_t lo, size_t hi)
+{
+	if (lo < hi) {
+		size_t p = __partition(a, lo, hi);
+		__qsort(a, lo, p - 1);
+		__qsort(a, p + 1, hi);
+	}
+}
-- 
cgit v1.2.1