1 files changed, 54 insertions, 0 deletions
diff --git a/src/sort.h b/src/sort.h
new file mode 100644
index 0000000..64a5b3e
--- /dev/null
+++ b/src/sort.h
@@ -0,0 +1,54 @@
+#ifndef ALGDS_SORT_H_
+#define ALGDS_SORT_H_
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "type_alias.h"
+
+#define QSORT_DEF(T) \
+    void T##_qsort(T* arr, int n);
+
+#define QSORT_IMPL(T) \
+    void T##_qsort_swap(T* arr, int lhs, int rhs) { \
+        if (lhs == rhs) return; \
+        T buf; \
+        memcpy(&buf, arr+lhs, sizeof(T)); \
+        memcpy(arr+lhs, arr+rhs, sizeof(T)); \
+        memcpy(arr+rhs, &buf, sizeof(T)); \
+    } \
+    void T##_qsort(T* arr, int n) { \
+        if (n <= 1) return; \
+        int pivot = rand() % n; \
+        T##_qsort_swap(arr, 0, pivot); \
+        int lp = 1, rp = n-1; \
+        while (lp < rp) { \
+            if (T##_cmp(arr+lp, arr) < 0) { \
+                lp++; \
+                continue; \
+            } \
+            if (T##_cmp(arr+rp, arr) >= 0) { \
+                rp--; \
+                continue; \
+            } \
+            T##_qsort_swap(arr, lp, rp); \
+            lp++; \
+            rp--; \
+        } \
+        if (T##_cmp(arr + rp, arr) > 0) rp--; \
+        T##_qsort_swap(arr, 0, rp); \
+        T##_qsort(arr, rp); \
+        T##_qsort(arr+rp+1, n-rp-1); \
+    }
+
+QSORT_DEF(Int);
+QSORT_DEF(Bool);
+QSORT_DEF(Long);
+QSORT_DEF(Char);
+QSORT_DEF(UInt);
+QSORT_DEF(ULong);
+QSORT_DEF(Double);
+QSORT_DEF(Float);
+QSORT_DEF(String);
+
+#endif