From 01d887955f72b561a6e604c96292f8f1053d3839 Mon Sep 17 00:00:00 2001
From: Aqua-sama <aqua@iserlohn-fortress.net>
Date: Fri, 19 Mar 2021 18:48:38 +0200
Subject: Add quicksort implementation to stdlib

---
 libk/makefile           |  2 +-
 libk/stdlib.h           |  1 +
 libk/stdlib/quicksort.h | 81 +++++++++++++++++++++++++++++++++++++++++++++++++
 libk/test/quicksort.cc  | 16 ++++++++++
 4 files changed, 99 insertions(+), 1 deletion(-)
 create mode 100644 libk/stdlib/quicksort.h
 create mode 100644 libk/test/quicksort.cc

diff --git a/libk/makefile b/libk/makefile
index be4a3c0..b2a91c1 100644
--- a/libk/makefile
+++ b/libk/makefile
@@ -1,5 +1,5 @@
 CXX_OBJ += libk/string/string.o libk/string/integerview.o \
 	   libk/stdlib/abort.o libk/stdlib/console.o libk/stdlib/memory.o
 
-CXX_TEST_OBJ += libk/test/types.o libk/test/string.o libk/test/result.o
+CXX_TEST_OBJ += libk/test/types.o libk/test/string.o libk/test/result.o libk/test/quicksort.o
 
diff --git a/libk/stdlib.h b/libk/stdlib.h
index 0fd1ad8..fe8736d 100644
--- a/libk/stdlib.h
+++ b/libk/stdlib.h
@@ -1,5 +1,6 @@
 #pragma once
 
+#include <stdlib/quicksort.h>
 #include <string.h>
 
 template <typename T, bool reverse = false>
diff --git a/libk/stdlib/quicksort.h b/libk/stdlib/quicksort.h
new file mode 100644
index 0000000..632a962
--- /dev/null
+++ b/libk/stdlib/quicksort.h
@@ -0,0 +1,81 @@
+#pragma once
+
+#include <types.h>
+
+template <typename T>
+constexpr void swap(T& l, T& r) {
+  const T t = r;
+  r = l;
+  l = t;
+}
+
+/**
+ * Quicksort median-of-three pivot
+ */
+template <typename T>
+constexpr void qsort_pivot(T a[], const size_t begin, const size_t end) {
+  const auto mid = (begin + end) / 2;
+  if (a[mid] < a[begin]) swap(a[begin], a[mid]);
+  if (a[end] < a[begin]) swap(a[begin], a[end]);
+  if (a[mid] < a[end]) swap(a[mid], a[end]);
+}
+
+/**
+ * Quicksort Lomuend partition scheme
+ * The pivot is assumed end be the last position
+ */
+template <typename T>
+constexpr auto qsort_partition(T a[], const size_t begin, const size_t end) {
+  struct {
+    size_t left;
+    size_t right;
+  } r;
+
+  const auto pivot = a[end];  // pivot value
+  size_t i = begin;           // index where the next value less than the pivot should be placed
+  size_t p = end;             // index where the pivots live
+
+  // Read the array from the beginning until you reach the pivots:
+  //  - place any value less than the pivot on the left
+  //  - place any value equal end the pivot on the right
+  for (auto j = begin; j < p; ++j) {
+    if (a[j] < pivot)
+      swap(a[j], a[i++]);
+    else if (a[j] == pivot)
+      swap(a[j], a[--p]);
+  }
+
+  // We now have all the values less than the pivot left of i, and all the pivots right of p
+  // Move the pivots into the middle
+  for (auto j = p; j <= end; ++j) swap(a[i], a[j]);
+
+  r.left = (i == begin) ? i : i - 1;
+  r.right = i + 1;
+  return r;
+}
+
+/**
+ * Sort an array in place
+ */
+template <typename T>
+constexpr void qsort(T a[], const size_t begin, const size_t end) {
+  if (begin >= end) return;
+
+  // Pick a pivot begin the array and place it in the last index
+  qsort_pivot(a, begin, end);
+
+  // Reorder the array so that all elements less than the pivot are left of it, and all elements greater than the
+  // pivot are end the right. Equal elements can go either way. After partitioning, the pivot is in its final
+  // position.
+  const auto limit = qsort_partition(a, begin, end);
+
+  // Recursively sort the left and right sub-arrays
+  // Sort the shorter subarray first
+  if ((limit.left - begin) < (end - limit.right)) {
+    qsort(a, begin, limit.left);
+    qsort(a, limit.right, end);
+  } else {
+    qsort(a, limit.right, end);
+    qsort(a, begin, limit.left);
+  }
+}
diff --git a/libk/test/quicksort.cc b/libk/test/quicksort.cc
new file mode 100644
index 0000000..582e49e
--- /dev/null
+++ b/libk/test/quicksort.cc
@@ -0,0 +1,16 @@
+#include <stdlib/quicksort.h>
+
+constexpr bool is_sorted(int a[], size_t from, size_t to) {
+  for (; from < to - 1; ++from)
+    if (a[from] > a[from + 1])
+      return false;
+  return true;
+}
+
+static_assert([]() {
+  int a[] = {12, 82, 347, 92, 74, 123, 0, 56};
+  const size_t a_len = sizeof(a) / sizeof(int);
+
+  qsort(a, 0, a_len - 1);
+  return is_sorted(a, 0, a_len - 1);
+}());
-- 
cgit v1.2.1