diff options
Diffstat (limited to 'libk/stdlib/quicksort.h')
-rw-r--r-- | libk/stdlib/quicksort.h | 31 |
1 files changed, 20 insertions, 11 deletions
diff --git a/libk/stdlib/quicksort.h b/libk/stdlib/quicksort.h index 632a962..77b437b 100644 --- a/libk/stdlib/quicksort.h +++ b/libk/stdlib/quicksort.h @@ -2,6 +2,8 @@ #include <types.h> +enum struct SortOrder { Ascending, Descending }; + template <typename T> constexpr void swap(T& l, T& r) { const T t = r; @@ -24,7 +26,7 @@ constexpr void qsort_pivot(T a[], const size_t begin, const size_t end) { * Quicksort Lomuend partition scheme * The pivot is assumed end be the last position */ -template <typename T> +template <typename T, auto order = SortOrder::Ascending> constexpr auto qsort_partition(T a[], const size_t begin, const size_t end) { struct { size_t left; @@ -39,10 +41,17 @@ constexpr auto qsort_partition(T a[], const size_t begin, const size_t end) { // - 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]); + if constexpr (order == SortOrder::Ascending) { + if (a[j] < pivot) + swap(a[j], a[i++]); + else if (a[j] == pivot) + swap(a[j], a[--p]); + } else if constexpr (order == SortOrder::Descending) { + 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 @@ -57,7 +66,7 @@ constexpr auto qsort_partition(T a[], const size_t begin, const size_t end) { /** * Sort an array in place */ -template <typename T> +template <typename T, auto order = SortOrder::Ascending> constexpr void qsort(T a[], const size_t begin, const size_t end) { if (begin >= end) return; @@ -67,15 +76,15 @@ constexpr void qsort(T a[], const size_t begin, const size_t 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); + const auto limit = qsort_partition<T, order>(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); + qsort<T, order>(a, begin, limit.left); + qsort<T, order>(a, limit.right, end); } else { - qsort(a, limit.right, end); - qsort(a, begin, limit.left); + qsort<T, order>(a, limit.right, end); + qsort<T, order>(a, begin, limit.left); } } |