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