-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmain.cpp
More file actions
100 lines (77 loc) · 2.24 KB
/
Copy pathmain.cpp
File metadata and controls
100 lines (77 loc) · 2.24 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <concepts>
#include <cstdlib>
#include <print>
#include <ranges>
#include <stdexcept>
#include <utility>
template <typename T>
concept Sortable = std::totally_ordered<T> && std::movable<T>;
template <typename T>
[[nodiscard]] constexpr T medianOfThreePivot(std::span<T> arr) {
if (arr.size() < 2) {
throw std::invalid_argument("span size must be at least 2");
}
size_t low = 0;
size_t high = arr.size() - 1;
size_t mid = high / 2;
// Sort the three elements at low, mid, and high
if (arr[mid] < arr[low]) std::swap(arr[mid], arr[low]);
if (arr[high] < arr[low]) std::swap(arr[high], arr[low]);
if (arr[high] < arr[mid]) std::swap(arr[high], arr[mid]);
// Place the median just before the last element as the pivot
std::swap(arr[mid], arr[high - 1]);
return arr[high - 1]; // Return the pivot value
}
template <Sortable T>
[[nodiscard]] constexpr size_t partition(std::span<T> arr) {
if (arr.size() <= 2) return 0;
T pivot = medianOfThreePivot(arr);
size_t low = 0;
size_t high = arr.size() - 1;
size_t i = low;
size_t j = high - 1;
while (true) {
while (arr[i] < pivot) i++;
while (pivot < arr[j]) j--;
if (i >= j) break;
std::swap(arr[i], arr[j]);
i++;
j--;
}
// Ensuring pivot is at its correct position
if (i < high) {
std::swap(arr[i], arr[high - 1]);
}
return i;
}
template <typename Range>
concept SortableRange = std::ranges::random_access_range<Range> &&
Sortable<std::ranges::range_value_t<Range>>;
template <SortableRange Range>
constexpr void quick_sort(Range&& range) {
quick_sort(std::span{std::forward<Range>(range)});
}
template <Sortable T>
constexpr void quick_sort(std::span<T> arr) {
if (arr.size() < 2) return;
const size_t p = partition(arr);
if (p > 0) {
quick_sort(arr.subspan(0, p));
}
quick_sort(arr.subspan(p + 1));
}
int main() {
std::array<int, 7> arr = {3, 6, 8, 10, 1, 2, 1};
auto print_array = [](const auto& container) {
for (const auto& elem : std::views::all(container)) {
std::print("{} ", elem);
}
std::println("");
};
std::println("Original array: ");
print_array(arr);
quick_sort<int>(arr);
std::println("Sorted array: ");
print_array(arr);
return EXIT_SUCCESS;
}