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