| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "votincev_d_radixmerge_sort/seq/include/ops_seq.hpp" | ||
| 2 | |||
| 3 | #include <algorithm> | ||
| 4 | #include <array> | ||
| 5 | #include <cstddef> | ||
| 6 | #include <cstdint> | ||
| 7 | #include <utility> | ||
| 8 | #include <vector> | ||
| 9 | |||
| 10 | #include "votincev_d_radixmerge_sort/common/include/common.hpp" | ||
| 11 | |||
| 12 | namespace votincev_d_radixmerge_sort { | ||
| 13 | |||
| 14 |
1/2✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
|
80 | VotincevDRadixMergeSortSEQ::VotincevDRadixMergeSortSEQ(const InType &in) { |
| 15 | SetTypeOfTask(GetStaticTypeOfTask()); | ||
| 16 |
1/2✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
|
80 | GetInput() = in; |
| 17 | 80 | } | |
| 18 | |||
| 19 | 80 | bool VotincevDRadixMergeSortSEQ::ValidationImpl() { | |
| 20 | 80 | return !GetInput().empty(); | |
| 21 | } | ||
| 22 | |||
| 23 | 80 | bool VotincevDRadixMergeSortSEQ::PreProcessingImpl() { | |
| 24 | 80 | return true; | |
| 25 | } | ||
| 26 | |||
| 27 | // поразрядная сортировка | ||
| 28 | 168 | void VotincevDRadixMergeSortSEQ::SortByDigit(std::vector<int32_t> &array, int32_t exp) { | |
| 29 | size_t n = array.size(); | ||
| 30 | 168 | std::vector<int32_t> output(n); | |
| 31 | 168 | std::array<int32_t, 10> count{}; | |
| 32 | |||
| 33 |
2/2✓ Branch 0 taken 104000 times.
✓ Branch 1 taken 168 times.
|
104168 | for (size_t i = 0; i < n; i++) { |
| 34 | 104000 | int32_t digit = (array[i] / exp) % 10; | |
| 35 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 104000 times.
|
104000 | count.at(static_cast<size_t>(digit))++; |
| 36 | } | ||
| 37 | |||
| 38 | // префиксные суммы | ||
| 39 |
2/2✓ Branch 0 taken 1512 times.
✓ Branch 1 taken 168 times.
|
1680 | for (size_t i = 1; i < 10; i++) { |
| 40 | 1512 | count.at(i) += count.at(i - 1); | |
| 41 | } | ||
| 42 | |||
| 43 | // формирую выходной массив | ||
| 44 |
2/2✓ Branch 0 taken 104000 times.
✓ Branch 1 taken 168 times.
|
104168 | for (int64_t i = static_cast<int64_t>(n) - 1; i >= 0; i--) { |
| 45 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 104000 times.
|
104000 | auto idx = static_cast<size_t>(i); |
| 46 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 104000 times.
|
104000 | auto digit = static_cast<size_t>((array.at(idx) / exp) % 10); |
| 47 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 104000 times.
|
104000 | size_t pos = static_cast<size_t>(count.at(digit)) - 1; |
| 48 | 104000 | output.at(pos) = array.at(idx); | |
| 49 | 104000 | count.at(digit)--; | |
| 50 | } | ||
| 51 | |||
| 52 | array = std::move(output); | ||
| 53 | 168 | } | |
| 54 | |||
| 55 | 80 | bool VotincevDRadixMergeSortSEQ::RunImpl() { | |
| 56 | 80 | std::vector<int32_t> working_array = GetInput(); | |
| 57 | |||
| 58 | auto [min_it, max_it] = std::ranges::minmax_element(working_array); | ||
| 59 | 80 | int32_t min_val = *min_it; | |
| 60 | 80 | int32_t max_val = *max_it; | |
| 61 | |||
| 62 | // сдвиг в положительную область | ||
| 63 |
2/2✓ Branch 0 taken 40 times.
✓ Branch 1 taken 40 times.
|
80 | if (min_val < 0) { |
| 64 |
2/2✓ Branch 0 taken 40800 times.
✓ Branch 1 taken 40 times.
|
40840 | for (auto &num : working_array) { |
| 65 | 40800 | num -= min_val; | |
| 66 | } | ||
| 67 | 40 | max_val -= min_val; | |
| 68 | } | ||
| 69 | |||
| 70 | // цикл по разрядам | ||
| 71 |
2/2✓ Branch 0 taken 168 times.
✓ Branch 1 taken 80 times.
|
248 | for (int64_t exp = 1; static_cast<int64_t>(max_val) / exp > 0; exp *= 10) { |
| 72 |
1/2✓ Branch 1 taken 168 times.
✗ Branch 2 not taken.
|
168 | SortByDigit(working_array, static_cast<int32_t>(exp)); |
| 73 | } | ||
| 74 | |||
| 75 | // возврат к исходному диапазону | ||
| 76 |
2/2✓ Branch 0 taken 40 times.
✓ Branch 1 taken 40 times.
|
80 | if (min_val < 0) { |
| 77 |
2/2✓ Branch 0 taken 40800 times.
✓ Branch 1 taken 40 times.
|
40840 | for (auto &num : working_array) { |
| 78 | 40800 | num += min_val; | |
| 79 | } | ||
| 80 | } | ||
| 81 | |||
| 82 | GetOutput() = std::move(working_array); | ||
| 83 | 80 | return true; | |
| 84 | } | ||
| 85 | |||
| 86 | 80 | bool VotincevDRadixMergeSortSEQ::PostProcessingImpl() { | |
| 87 | 80 | return true; | |
| 88 | } | ||
| 89 | |||
| 90 | } // namespace votincev_d_radixmerge_sort | ||
| 91 |