GCC Code Coverage Report

Directory: ./
File: tasks/trofimov_n_hoar_sort_batcher/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 43 43 100.0%
Functions: 8 8 100.0%
Branches: 29 34 85.3%
Line Branch Exec Source
1 #include "trofimov_n_hoar_sort_batcher/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <stack>
5 #include <utility>
6 #include <vector>
7
8 #include "trofimov_n_hoar_sort_batcher/common/include/common.hpp"
9
10 namespace trofimov_n_hoar_sort_batcher {
11
12 namespace {
13
14 416 int HoarePartition(std::vector<int> &arr, int left, int right) {
15 416 int pivot = arr[left + ((right - left) / 2)];
16 416 int i = left - 1;
17 416 int j = right + 1;
18
19 while (true) {
20 650 ++i;
21
2/2
✓ Branch 0 taken 320 times.
✓ Branch 1 taken 650 times.
 970 while (arr[i] < pivot) {
22 320 ++i;
23 }
24 650 --j;
25
2/2
✓ Branch 0 taken 368 times.
✓ Branch 1 taken 650 times.
 1018 while (arr[j] > pivot) {
26 368 --j;
27 }
28
2/2
✓ Branch 0 taken 416 times.
✓ Branch 1 taken 234 times.
 650 if (i >= j) {
29 416 return j;
30 }
31 std::swap(arr[i], arr[j]);
32 }
33 }
34
35 void CompareExchange(int &a, int &b) {
36
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 888 times.
 1016 if (a > b) {
37 std::swap(a, b);
38 }
39 }
40
41 416 void OddEvenMergeIter(std::vector<int> &arr, int left, int right) {
42 416 int n = right - left + 1;
43
2/2
✓ Branch 0 taken 750 times.
✓ Branch 1 taken 416 times.
 1166 for (int step = 1; step < n; step *= 2) {
44
2/2
✓ Branch 0 taken 1016 times.
✓ Branch 1 taken 750 times.
 1766 for (int i = left; i + step <= right; i += step * 2) {
45
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 888 times.
 1016 CompareExchange(arr[i], arr[i + step]);
46 }
47 }
48 416 }
49
50 82 void QuickBatcherIterative(std::vector<int> &arr, int left, int right) {
51 std::stack<std::pair<int, int>> stk;
52 stk.emplace(left, right);
53
54
2/2
✓ Branch 0 taken 914 times.
✓ Branch 1 taken 82 times.
 996 while (!stk.empty()) {
55 auto [l, r] = stk.top();
56 stk.pop();
57
2/2
✓ Branch 0 taken 498 times.
✓ Branch 1 taken 416 times.
 914 if (l >= r) {
58 498 continue;
59 }
60
61 416 int pivot_index = HoarePartition(arr, l, r);
62
63
2/2
✓ Branch 0 taken 164 times.
✓ Branch 1 taken 252 times.
 416 if (pivot_index - l > r - pivot_index - 1) {
64 stk.emplace(l, pivot_index);
65
1/2
✓ Branch 1 taken 164 times.
✗ Branch 2 not taken.
 164 stk.emplace(pivot_index + 1, r);
66 } else {
67
2/4
✓ Branch 1 taken 252 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 252 times.
✗ Branch 5 not taken.
 252 stk.emplace(pivot_index + 1, r);
68 stk.emplace(l, pivot_index);
69 }
70
71 416 OddEvenMergeIter(arr, l, r);
72 }
73 82 }
74
75 } // namespace
76
77
1/2
✓ Branch 1 taken 98 times.
✗ Branch 2 not taken.
 98 TrofimovNHoarSortBatcherSEQ::TrofimovNHoarSortBatcherSEQ(const InType &in) {
78 SetTypeOfTask(GetStaticTypeOfTask());
79
1/2
✓ Branch 1 taken 98 times.
✗ Branch 2 not taken.
 98 GetInput() = in;
80 98 }
81
82 98 bool TrofimovNHoarSortBatcherSEQ::ValidationImpl() {
83 98 return true;
84 }
85
86 98 bool TrofimovNHoarSortBatcherSEQ::PreProcessingImpl() {
87 98 GetOutput() = GetInput();
88 98 return true;
89 }
90
91
2/2
✓ Branch 0 taken 82 times.
✓ Branch 1 taken 16 times.
 98 bool TrofimovNHoarSortBatcherSEQ::RunImpl() {
92 auto &data = GetOutput();
93
2/2
✓ Branch 0 taken 82 times.
✓ Branch 1 taken 16 times.
 98 if (data.size() > 1) {
94 82 QuickBatcherIterative(data, 0, static_cast<int>(data.size()) - 1);
95 }
96 98 return true;
97 }
98
99 98 bool TrofimovNHoarSortBatcherSEQ::PostProcessingImpl() {
100 98 return true;
101 }
102
103 } // namespace trofimov_n_hoar_sort_batcher
104