GCC Code Coverage Report

Directory: ./
File: tasks/krasnopevtseva_v_hoare_batcher_sort/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 55 96 57.3%
Functions: 9 12 75.0%
Branches: 29 62 46.8%
Line Branch Exec Source
1 #include "krasnopevtseva_v_hoare_batcher_sort/all/include/ops_all.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <cstddef>
8 #include <stack>
9 #include <utility>
10 #include <vector>
11
12 #include "krasnopevtseva_v_hoare_batcher_sort/common/include/common.hpp"
13
14 namespace krasnopevtseva_v_hoare_batcher_sort {
15
16
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 KrasnopevtsevaVHoareBatcherSortALL::KrasnopevtsevaVHoareBatcherSortALL(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetInput() = in;
19 12 GetOutput() = std::vector<int>();
20 12 }
21
22 12 bool KrasnopevtsevaVHoareBatcherSortALL::ValidationImpl() {
23 const auto &input = GetInput();
24 12 return !input.empty();
25 }
26
27 12 bool KrasnopevtsevaVHoareBatcherSortALL::PreProcessingImpl() {
28 12 GetOutput() = std::vector<int>();
29 12 return true;
30 }
31
32 12 bool KrasnopevtsevaVHoareBatcherSortALL::PostProcessingImpl() {
33 12 return true;
34 }
35
36 26 int KrasnopevtsevaVHoareBatcherSortALL::Partition(std::vector<int> &arr, int first, int last) {
37 26 int i = first - 1;
38 26 int value = arr[last];
39
40
2/2
✓ Branch 0 taken 628 times.
✓ Branch 1 taken 26 times.
 654 for (int j = first; j <= last - 1; ++j) {
41
2/2
✓ Branch 0 taken 258 times.
✓ Branch 1 taken 370 times.
 628 if (arr[j] <= value) {
42 258 ++i;
43 258 std::swap(arr[i], arr[j]);
44 }
45 }
46 26 std::swap(arr[i + 1], arr[last]);
47 26 return i + 1;
48 }
49
50 20 void KrasnopevtsevaVHoareBatcherSortALL::InsertionSort(std::vector<int> &arr, int first, int last) {
51
2/2
✓ Branch 0 taken 202 times.
✓ Branch 1 taken 20 times.
 222 for (int i = first + 1; i <= last; ++i) {
52 202 int key = arr[i];
53 202 int j = i - 1;
54
4/4
✓ Branch 0 taken 770 times.
✓ Branch 1 taken 50 times.
✓ Branch 2 taken 618 times.
✓ Branch 3 taken 152 times.
 820 while (j >= first && arr[j] > key) {
55 618 arr[j + 1] = arr[j];
56 618 --j;
57 }
58 202 arr[j + 1] = key;
59 }
60 20 }
61
62 12 void KrasnopevtsevaVHoareBatcherSortALL::QuickSort(std::vector<int> &arr, int first, int last) {
63 std::stack<std::pair<int, int>> stack;
64 stack.emplace(first, last);
65
66
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 12 times.
 76 while (!stack.empty()) {
67 auto [l, r] = stack.top();
68 stack.pop();
69
70
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 46 times.
 64 if (l >= r) {
71 38 continue;
72 }
73
74
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 26 times.
 46 if (r - l < 16) {
75 20 InsertionSort(arr, l, r);
76 20 continue;
77 }
78
79 26 int iter = Partition(arr, l, r);
80
81
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 12 times.
 26 if (iter - l < r - iter) {
82
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 stack.emplace(iter + 1, r);
83
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 stack.emplace(l, iter - 1);
84 } else {
85
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 stack.emplace(l, iter - 1);
86
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 stack.emplace(iter + 1, r);
87 }
88 }
89 12 }
90
91 ✗ void KrasnopevtsevaVHoareBatcherSortALL::BatcherMergeBlocksStep(int *left_pointer, int &left_size, int *right_pointer,
92 int &right_size) {
93 ✗ std::inplace_merge(left_pointer, right_pointer, right_pointer + right_size);
94 ✗ left_size += right_size;
95 ✗ }
96
97 ✗ void KrasnopevtsevaVHoareBatcherSortALL::BatcherMerge(int thread_input_size, std::vector<int *> &pointers,
98 std::vector<int> &sizes, int par_if_greater) {
99 ✗ int pack = static_cast<int>(pointers.size());
100 ✗ for (int step = 1; pack > 1; step *= 2, pack /= 2) {
101 ✗ bool do_parallel = (thread_input_size / step) > par_if_greater;
102
103 ✗ if (do_parallel) {
104 ✗ #pragma omp parallel for default(none) shared(pointers, sizes, pack, step)
105 for (int off = 0; off < pack / 2; ++off) {
106 auto idx1 = static_cast<std::size_t>(2 * step) * static_cast<std::size_t>(off);
107 auto idx2 = idx1 + static_cast<std::size_t>(step);
108 BatcherMergeBlocksStep(pointers[idx1], sizes[idx1], pointers[idx2], sizes[idx2]);
109 }
110 } else {
111 ✗ for (int off = 0; off < pack / 2; ++off) {
112 ✗ auto idx1 = static_cast<std::size_t>(2 * step) * static_cast<std::size_t>(off);
113 ✗ auto idx2 = idx1 + static_cast<std::size_t>(step);
114 ✗ BatcherMergeBlocksStep(pointers[idx1], sizes[idx1], pointers[idx2], sizes[idx2]);
115 }
116 }
117
118 ✗ if ((pack / 2) - 1 == 0) {
119 ✗ BatcherMergeBlocksStep(pointers[0], sizes[sizes.size() - 1], pointers[pointers.size() - 1],
120 sizes[sizes.size() - 1]);
121 ✗ } else if ((pack / 2) % 2 != 0) {
122 ✗ auto idx1 = static_cast<std::size_t>(2 * step) * static_cast<std::size_t>((pack / 2) - 2);
123 ✗ auto idx2 = static_cast<std::size_t>(2 * step) * static_cast<std::size_t>((pack / 2) - 1);
124 ✗ BatcherMergeBlocksStep(pointers[idx1], sizes[idx1], pointers[idx2], sizes[idx2]);
125 }
126 }
127 ✗ }
128
129 ✗ void KrasnopevtsevaVHoareBatcherSortALL::ParallelSortChunks(std::vector<int> &arr, int n, int numthreads) {
130 ✗ if (n <= 0) {
131 ✗ return;
132 }
133
134 ✗ numthreads = std::min(n, numthreads);
135 ✗ if (numthreads <= 0) {
136 ✗ numthreads = 1;
137 }
138
139 ✗ int thread_input_size = n / numthreads;
140 ✗ int thread_input_remainder_size = n % numthreads;
141
142 ✗ std::vector<int *> pointers(numthreads);
143 ✗ std::vector<int> sizes(numthreads);
144
145 ✗ for (int i = 0; i < numthreads; ++i) {
146 ✗ std::ptrdiff_t offset = static_cast<std::ptrdiff_t>(i) * static_cast<std::ptrdiff_t>(thread_input_size);
147 ✗ pointers[i] = arr.data() + offset;
148 ✗ sizes[i] = thread_input_size;
149 }
150 ✗ sizes.back() += thread_input_remainder_size;
151
152 ✗ #pragma omp parallel for default(none) shared(arr, pointers, sizes, numthreads)
153 for (int i = 0; i < numthreads; ++i) {
154 int left = static_cast<int>(pointers[i] - arr.data());
155 int right = left + sizes[i] - 1;
156 if (left < right) {
157 QuickSort(arr, left, right);
158 }
159 }
160
161 ✗ BatcherMerge(thread_input_size, pointers, sizes, 32);
162 }
163
164
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 void KrasnopevtsevaVHoareBatcherSortALL::SortLocalData(std::vector<int> &data) {
165 12 int n = static_cast<int>(data.size());
166
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (n <= 0) {
167 ✗ return;
168 }
169
170 12 int numthreads = omp_get_max_threads();
171 12 numthreads = std::min(n, numthreads);
172
173
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (n < 1000) {
174 12 QuickSort(data, 0, n - 1);
175 } else {
176 ✗ ParallelSortChunks(data, n, numthreads);
177 }
178 }
179
180 12 bool KrasnopevtsevaVHoareBatcherSortALL::RunImpl() {
181 const auto &input = GetInput();
182 12 std::vector<int> result = input;
183
184
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (result.size() <= 1) {
185 ✗ GetOutput() = result;
186 return true;
187 }
188
189
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 SortLocalData(result);
190 GetOutput() = std::move(result);
191 12 return true;
192 }
193
194 } // namespace krasnopevtseva_v_hoare_batcher_sort
195