diff options
author | Aqua-sama <aqua@iserlohn-fortress.net> | 2021-03-19 18:48:38 +0200 |
---|---|---|
committer | Aqua-sama <aqua@iserlohn-fortress.net> | 2021-03-19 18:48:38 +0200 |
commit | 01d887955f72b561a6e604c96292f8f1053d3839 (patch) | |
tree | 4902f84aee401684c3864d9b475ed57344296c25 /libk/stdlib | |
parent | cpuid: show manufacturer and model (diff) | |
download | kernel.cpp-01d887955f72b561a6e604c96292f8f1053d3839.tar.xz |
Add quicksort implementation to stdlib
Diffstat (limited to 'libk/stdlib')
-rw-r--r-- | libk/stdlib/quicksort.h | 81 |
1 files changed, 81 insertions, 0 deletions
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); + } +} |