GCC Code Coverage Report

Directory: ./
File: tasks/shekhirev_v_hoare_batcher_sort_seq/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 64 65 98.5%
Functions: 8 8 100.0%
Branches: 49 66 74.2%
Line Branch Exec Source
1 #include "shekhirev_v_hoare_batcher_sort_seq/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <climits>
5 #include <cstddef>
6 #include <tuple>
7 #include <utility>
8 #include <vector>
9
10 #include "shekhirev_v_hoare_batcher_sort_seq/common/include/common.hpp"
11
12 namespace shekhirev_v_hoare_batcher_sort_seq {
13
14 namespace {
15
16 3200 int HoarePartition(std::vector<int> &arr, int left, int right) {
17 3200 int pivot = arr[left + ((right - left) / 2)];
18 int i = left;
19 int j = right;
20
21
2/2
✓ Branch 0 taken 7320 times.
✓ Branch 1 taken 3200 times.
 13720 while (i <= j) {
22
2/2
✓ Branch 0 taken 6544 times.
✓ Branch 1 taken 7320 times.
 13864 while (arr[i] < pivot) {
23 6544 i++;
24 }
25
2/2
✓ Branch 0 taken 7784 times.
✓ Branch 1 taken 7320 times.
 15104 while (arr[j] > pivot) {
26 7784 j--;
27 }
28
2/2
✓ Branch 0 taken 760 times.
✓ Branch 1 taken 6560 times.
 7320 if (i <= j) {
29 std::swap(arr[i], arr[j]);
30 6560 i++;
31 6560 j--;
32 }
33 }
34 3200 return i;
35 }
36
37 void BatcherComp(std::vector<int> &arr, int left, int right, int r, int m) {
38
2/2
✓ Branch 0 taken 8896 times.
✓ Branch 1 taken 1600 times.
 10496 for (int i = left + r; i + r <= right; i += m) {
39
2/2
✓ Branch 0 taken 4352 times.
✓ Branch 1 taken 4544 times.
 8896 if (arr[i] > arr[i + r]) {
40 std::swap(arr[i], arr[i + r]);
41 }
42 }
43 }
44
45 } // namespace
46
47
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 ShekhirevHoareBatcherSortSEQ::ShekhirevHoareBatcherSortSEQ(const InType &in) {
48 SetTypeOfTask(GetStaticTypeOfTask());
49
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
50 GetOutput().clear();
51 48 }
52
53 48 bool ShekhirevHoareBatcherSortSEQ::ValidationImpl() {
54 48 return true;
55 }
56
57
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 bool ShekhirevHoareBatcherSortSEQ::PreProcessingImpl() {
58 const auto &in = GetInput();
59
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 if (in.empty()) {
60 GetOutput().clear();
61 8 return true;
62 }
63
64 size_t original_size = in.size();
65 size_t p2 = 1;
66
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 40 times.
 216 while (p2 < original_size) {
67 176 p2 *= 2;
68 }
69
70 40 GetOutput() = in;
71 40 GetOutput().resize(p2, INT_MAX);
72 40 return true;
73 }
74
75 64 void ShekhirevHoareBatcherSortSEQ::HoareSort(std::vector<int> &arr, int start_left, int start_right) {
76 64 std::vector<std::pair<int, int>> stk;
77
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 stk.reserve(32);
78
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 stk.emplace_back(start_left, start_right);
79
80
2/2
✓ Branch 0 taken 3200 times.
✓ Branch 1 taken 64 times.
 3264 while (!stk.empty()) {
81 auto [left, right] = stk.back();
82 stk.pop_back();
83
84
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3200 times.
 3200 if (left >= right) {
85 ✗ continue;
86 }
87
88 3200 int partition_index = HoarePartition(arr, left, right);
89
2/2
✓ Branch 0 taken 1504 times.
✓ Branch 1 taken 1696 times.
 3200 if (partition_index < right) {
90
1/2
✓ Branch 1 taken 1504 times.
✗ Branch 2 not taken.
 1504 stk.emplace_back(partition_index, right);
91 }
92
2/2
✓ Branch 0 taken 1632 times.
✓ Branch 1 taken 1568 times.
 3200 if (left < partition_index - 1) {
93
1/4
✓ Branch 1 taken 1632 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 1632 stk.emplace_back(left, partition_index - 1);
94 }
95 }
96 64 }
97
98 32 void ShekhirevHoareBatcherSortSEQ::BatcherMerge(std::vector<int> &arr, int start_left, int start_right, int start_r) {
99 32 std::vector<std::tuple<int, int, int, int>> stk;
100
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 stk.reserve(32);
101
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 stk.emplace_back(start_left, start_right, start_r, 0);
102
103
2/2
✓ Branch 0 taken 4832 times.
✓ Branch 1 taken 32 times.
 4864 while (!stk.empty()) {
104 auto [left, right, r, stage] = stk.back();
105 stk.pop_back();
106
107 4832 int n = right - left + 1;
108 4832 int m = r * 2;
109
110
2/2
✓ Branch 0 taken 3200 times.
✓ Branch 1 taken 1632 times.
 4832 if (m < n) {
111
2/2
✓ Branch 0 taken 1600 times.
✓ Branch 1 taken 1600 times.
 3200 if (stage == 0) {
112
1/2
✓ Branch 1 taken 1600 times.
✗ Branch 2 not taken.
 1600 stk.emplace_back(left, right, r, 1);
113
1/2
✓ Branch 1 taken 1600 times.
✗ Branch 2 not taken.
 1600 stk.emplace_back(left + r, right, m, 0);
114
1/4
✓ Branch 1 taken 1600 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 1600 stk.emplace_back(left, right, m, 0);
115 } else {
116 BatcherComp(arr, left, right, r, m);
117 }
118 } else {
119
1/2
✓ Branch 0 taken 1632 times.
✗ Branch 1 not taken.
 1632 if ((left + r) <= right) {
120
2/2
✓ Branch 0 taken 600 times.
✓ Branch 1 taken 1032 times.
 1632 if (arr[left] > arr[left + r]) {
121 std::swap(arr[left], arr[left + r]);
122 }
123 }
124 }
125 }
126 32 }
127
128
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 16 times.
 48 bool ShekhirevHoareBatcherSortSEQ::RunImpl() {
129 auto &data = GetOutput();
130
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 16 times.
 48 if (data.size() <= 1) {
131 return true;
132 }
133
134 32 int n = static_cast<int>(data.size());
135 32 int mid = n / 2;
136
137 32 HoareSort(data, 0, mid - 1);
138 32 HoareSort(data, mid, n - 1);
139 32 BatcherMerge(data, 0, n - 1, 1);
140
141 32 return true;
142 }
143
144 48 bool ShekhirevHoareBatcherSortSEQ::PostProcessingImpl() {
145 size_t original_size = GetInput().size();
146 48 GetOutput().resize(original_size);
147 48 return true;
148 }
149
150 } // namespace shekhirev_v_hoare_batcher_sort_seq
151