1//! @file sort.hpp
2//! @author ryftchen
3//! @brief The declarations (sort) in the algorithm module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2026 ryftchen. All rights reserved.
6
7#pragma once
8
9#include <algorithm>
10#include <array>
11#include <cmath>
12#include <cstdint>
13#include <numeric>
14#include <vector>
15
16//! @brief The algorithm module.
17namespace algorithm // NOLINT(modernize-concat-nested-namespaces)
18{
19//! @brief Sort-related functions in the algorithm module.
20namespace sort
21{
22//! @brief Brief function description.
23//! @return function description (module_function)
24inline static const char* description() noexcept
25{
26 return "ALGO_SORT";
27}
28extern const char* version() noexcept;
29
30//! @brief Sort methods.
31//! @tparam Elem - type of element
32template <typename Elem>
33class Sort
34{
35public:
36 //! @brief Bubble.
37 //! @param array - array to be sorted
38 //! @param length - length of array
39 //! @return array after sort
40 static std::vector<Elem> bubble(const Elem* const array, const std::uint32_t length);
41 //! @brief Selection.
42 //! @param array - array to be sorted
43 //! @param length - length of array
44 //! @return array after sort
45 static std::vector<Elem> selection(const Elem* const array, const std::uint32_t length);
46 //! @brief Insertion.
47 //! @param array - array to be sorted
48 //! @param length - length of array
49 //! @return array after sort
50 static std::vector<Elem> insertion(const Elem* const array, const std::uint32_t length);
51 //! @brief Shell.
52 //! @param array - array to be sorted
53 //! @param length - length of array
54 //! @return array after sort
55 static std::vector<Elem> shell(const Elem* const array, const std::uint32_t length);
56 //! @brief Merge.
57 //! @param array - array to be sorted
58 //! @param length - length of array
59 //! @return array after sort
60 static std::vector<Elem> merge(const Elem* const array, const std::uint32_t length);
61 //! @brief Quick.
62 //! @param array - array to be sorted
63 //! @param length - length of array
64 //! @return array after sort
65 static std::vector<Elem> quick(const Elem* const array, const std::uint32_t length);
66 //! @brief Heap.
67 //! @param array - array to be sorted
68 //! @param length - length of array
69 //! @return array after sort
70 static std::vector<Elem> heap(const Elem* const array, const std::uint32_t length);
71 //! @brief Counting.
72 //! @param array - array to be sorted
73 //! @param length - length of array
74 //! @return array after sort
75 static std::vector<Elem> counting(const Elem* const array, const std::uint32_t length)
76 requires std::is_integral_v<Elem>;
77 //! @brief Bucket.
78 //! @param array - array to be sorted
79 //! @param length - length of array
80 //! @return array after sort
81 static std::vector<Elem> bucket(const Elem* const array, const std::uint32_t length);
82 //! @brief Radix.
83 //! @param array - array to be sorted
84 //! @param length - length of array
85 //! @return array after sort
86 static std::vector<Elem> radix(const Elem* const array, const std::uint32_t length)
87 requires std::is_integral_v<Elem>;
88
89private:
90 //! @brief Recursion for the merge method.
91 //! @param sorting - array to be sorted
92 //! @param begin - index of beginning
93 //! @param end - index of ending
94 static void mergeSortRecursive(Elem* const sorting, const std::uint32_t begin, const std::uint32_t end);
95 //! @brief Recursion for the quick method.
96 //! @param sorting - array to be sorted
97 //! @param begin - index of beginning
98 //! @param end - index of ending
99 static void quickSortRecursive(Elem* const sorting, const std::uint32_t begin, const std::uint32_t end);
100 //! @brief Build maximum heap for the heap method.
101 //! @param sorting - array to be sorted
102 //! @param begin - index of beginning
103 //! @param end - index of ending
104 static void buildMaxHeap(Elem* const sorting, const std::uint32_t begin, const std::uint32_t end);
105};
106
107template <typename Elem>
108std::vector<Elem> Sort<Elem>::bubble(const Elem* const array, const std::uint32_t length)
109{
110 if (!array || (length == 0))
111 {
112 return {};
113 }
114
115 std::vector<Elem> sorting(array, array + length);
116 for (std::uint32_t i = 0; i < (length - 1); ++i)
117 {
118 for (std::uint32_t j = 0; j < (length - 1 - i); ++j)
119 {
120 if (sorting[j] > sorting[j + 1])
121 {
122 std::swap(sorting[j], sorting[j + 1]);
123 }
124 }
125 }
126 return sorting;
127}
128
129template <typename Elem>
130std::vector<Elem> Sort<Elem>::selection(const Elem* const array, const std::uint32_t length)
131{
132 if (!array || (length == 0))
133 {
134 return {};
135 }
136
137 std::vector<Elem> sorting(array, array + length);
138 for (std::uint32_t i = 0; i < (length - 1); ++i)
139 {
140 std::uint32_t min = i;
141 for (std::uint32_t j = i + 1; j < length; ++j)
142 {
143 if (sorting[j] < sorting[min])
144 {
145 min = j;
146 }
147 }
148 std::swap(sorting[i], sorting[min]);
149 }
150 return sorting;
151}
152
153template <typename Elem>
154std::vector<Elem> Sort<Elem>::insertion(const Elem* const array, const std::uint32_t length)
155{
156 if (!array || (length == 0))
157 {
158 return {};
159 }
160
161 std::vector<Elem> sorting(array, array + length);
162 for (std::uint32_t i = 1; i < length; ++i)
163 {
164 std::int64_t n = i - 1;
165 const Elem temp = sorting[i];
166 while ((n >= 0) && (sorting[n] > temp))
167 {
168 sorting[n + 1] = sorting[n];
169 --n;
170 }
171 sorting[n + 1] = temp;
172 }
173 return sorting;
174}
175
176template <typename Elem>
177std::vector<Elem> Sort<Elem>::shell(const Elem* const array, const std::uint32_t length)
178{
179 if (!array || (length == 0))
180 {
181 return {};
182 }
183
184 std::vector<Elem> sorting(array, array + length);
185 std::uint32_t gap = length / 2;
186 while (gap >= 1)
187 {
188 for (std::uint32_t i = gap; i < length; ++i)
189 {
190 for (std::uint32_t j = i; (j >= gap) && (sorting[j] < sorting[j - gap]); j -= gap)
191 {
192 std::swap(sorting[j], sorting[j - gap]);
193 }
194 }
195 gap /= 2;
196 }
197 return sorting;
198}
199
200template <typename Elem>
201std::vector<Elem> Sort<Elem>::merge(const Elem* const array, const std::uint32_t length)
202{
203 if (!array || (length == 0))
204 {
205 return {};
206 }
207
208 std::vector<Elem> sorting(array, array + length);
209 mergeSortRecursive(sorting: sorting.data(), begin: 0, end: length - 1);
210 return sorting;
211}
212
213template <typename Elem>
214void Sort<Elem>::mergeSortRecursive(Elem* const sorting, const std::uint32_t begin, const std::uint32_t end)
215{
216 if (begin >= end)
217 {
218 return;
219 }
220
221 const std::uint32_t mid = std::midpoint(a: begin, b: end);
222 mergeSortRecursive(sorting, begin, end: mid);
223 mergeSortRecursive(sorting, begin: mid + 1, end);
224
225 std::vector<Elem> leftPart(sorting + begin, sorting + mid + 1);
226 std::vector<Elem> rightPart(sorting + mid + 1, sorting + end + 1);
227 const std::uint32_t leftSize = leftPart.size();
228 const std::uint32_t rightSize = rightPart.size();
229 std::uint32_t leftIdx = 0;
230 std::uint32_t rightIdx = 0;
231 std::uint32_t pos = begin;
232 while ((leftIdx < leftSize) && (rightIdx < rightSize))
233 {
234 sorting[pos++] = (leftPart[leftIdx] < rightPart[rightIdx]) ? leftPart[leftIdx++] : rightPart[rightIdx++];
235 }
236
237 while (leftIdx < leftSize)
238 {
239 sorting[pos++] = leftPart[leftIdx++];
240 }
241 while (rightIdx < rightSize)
242 {
243 sorting[pos++] = rightPart[rightIdx++];
244 }
245}
246
247template <typename Elem>
248std::vector<Elem> Sort<Elem>::quick(const Elem* const array, const std::uint32_t length)
249{
250 if (!array || (length == 0))
251 {
252 return {};
253 }
254
255 std::vector<Elem> sorting(array, array + length);
256 quickSortRecursive(sorting: sorting.data(), begin: 0, end: length - 1);
257 return sorting;
258}
259
260template <typename Elem>
261void Sort<Elem>::quickSortRecursive(Elem* const sorting, const std::uint32_t begin, const std::uint32_t end)
262{
263 if (begin >= end)
264 {
265 return;
266 }
267
268 const Elem pivot = sorting[end];
269 std::uint32_t leftIdx = begin;
270 std::uint32_t rightIdx = end - 1;
271 while (leftIdx < rightIdx)
272 {
273 while ((leftIdx < rightIdx) && (sorting[leftIdx] < pivot))
274 {
275 ++leftIdx;
276 }
277 while ((leftIdx < rightIdx) && (sorting[rightIdx] >= pivot))
278 {
279 --rightIdx;
280 }
281 std::swap(sorting[leftIdx], sorting[rightIdx]);
282 }
283 if (sorting[leftIdx] >= sorting[end])
284 {
285 std::swap(sorting[leftIdx], sorting[end]);
286 }
287 else
288 {
289 ++leftIdx;
290 }
291
292 quickSortRecursive(sorting, begin, end: (leftIdx > 0) ? (leftIdx - 1) : 0);
293 quickSortRecursive(sorting, begin: leftIdx + 1, end);
294}
295
296template <typename Elem>
297std::vector<Elem> Sort<Elem>::heap(const Elem* const array, const std::uint32_t length)
298{
299 if (!array || (length == 0))
300 {
301 return {};
302 }
303
304 std::vector<Elem> sorting(array, array + length);
305 for (std::int64_t i = (length / 2) + 1; i >= 0; --i)
306 {
307 buildMaxHeap(sorting: sorting.data(), begin: i, end: length - 1);
308 }
309 for (std::int64_t i = length - 1; i > 0; --i)
310 {
311 std::swap(sorting[0], sorting[i]);
312 buildMaxHeap(sorting: sorting.data(), begin: 0, end: i - 1);
313 }
314 return sorting;
315}
316
317template <typename Elem>
318void Sort<Elem>::buildMaxHeap(Elem* const sorting, const std::uint32_t begin, const std::uint32_t end)
319{
320 std::uint32_t parent = begin;
321 std::uint32_t child = (parent * 2) + 1;
322 while (child <= end)
323 {
324 if (((child + 1) <= end) && (sorting[child] < sorting[child + 1]))
325 {
326 ++child;
327 }
328 if (sorting[parent] > sorting[child])
329 {
330 return;
331 }
332
333 std::swap(sorting[parent], sorting[child]);
334 parent = child;
335 child = parent * 2 + 1;
336 }
337}
338
339template <typename Elem>
340std::vector<Elem> Sort<Elem>::counting(const Elem* const array, const std::uint32_t length)
341requires std::is_integral_v<Elem>
342{
343 if (!array || (length == 0))
344 {
345 return {};
346 }
347
348 std::vector<Elem> sorting(array, array + length);
349 const Elem max = *std::ranges::max_element(sorting);
350 const Elem min = *std::ranges::min_element(sorting);
351 if (max == min)
352 {
353 return sorting;
354 }
355
356 const Elem countRange = max - min + 1;
357 std::vector<std::uint32_t> count(countRange, 0);
358 for (const auto elem : sorting)
359 {
360 ++count[elem - min];
361 }
362
363 std::uint32_t pos = 0;
364 for (Elem i = 0; i < countRange; ++i)
365 {
366 while (count[i]--)
367 {
368 sorting[pos++] = i + min;
369 }
370 }
371 return sorting;
372}
373
374template <typename Elem>
375std::vector<Elem> Sort<Elem>::bucket(const Elem* const array, const std::uint32_t length)
376{
377 if (!array || (length == 0))
378 {
379 return {};
380 }
381
382 std::vector<Elem> sorting(array, array + length);
383 const Elem max = *std::ranges::max_element(sorting);
384 const Elem min = *std::ranges::min_element(sorting);
385 if (max == min)
386 {
387 return sorting;
388 }
389
390 const std::uint32_t bucketNum = length;
391 std::vector<std::vector<Elem>> bucket(bucketNum);
392 for (const double interval = static_cast<double>(max - min) / static_cast<double>(bucketNum - 1);
393 const auto elem : sorting)
394 {
395 const std::uint32_t bucketIdx = std::floor(((elem - min) / interval) + 1) - 1;
396 bucket[bucketIdx].emplace_back(elem);
397 }
398
399 for (std::uint32_t pos = 0; auto& each : bucket)
400 {
401 std::ranges::sort(each);
402 for (const auto elem : each)
403 {
404 sorting[pos++] = elem;
405 }
406 }
407 return sorting;
408}
409
410template <typename Elem>
411std::vector<Elem> Sort<Elem>::radix(const Elem* const array, const std::uint32_t length)
412requires std::is_integral_v<Elem>
413{
414 if (!array || (length == 0))
415 {
416 return {};
417 }
418
419 std::vector<Elem> sorting(array, array + length);
420 const Elem min = *std::ranges::min_element(sorting);
421 const Elem max = *std::ranges::max_element(sorting);
422 if (max == min)
423 {
424 return sorting;
425 }
426
427 if (min < 0)
428 {
429 for (auto& elem : sorting)
430 {
431 elem -= min;
432 }
433 }
434
435 constexpr std::uint8_t base = 10;
436 for (Elem exp = 1; (max / exp) > 0; exp *= base)
437 {
438 std::vector<Elem> temp(length);
439 std::array<std::uint32_t, base> count{};
440 for (const auto elem : sorting)
441 {
442 const std::uint8_t digit = (elem / exp) % base;
443 ++count[digit];
444 }
445
446 for (std::uint8_t i = 1; i < base; ++i)
447 {
448 count[i] += count[i - 1];
449 }
450
451 for (std::int64_t i = length - 1; i >= 0; --i)
452 {
453 const std::uint8_t digit = (sorting[i] / exp) % base;
454 temp[--count[digit]] = sorting[i];
455 }
456 sorting = std::move(temp);
457 }
458
459 if (min < 0)
460 {
461 for (auto& elem : sorting)
462 {
463 elem += min;
464 }
465 }
466 return sorting;
467}
468} // namespace sort
469} // namespace algorithm
470