GCC Code Coverage Report

Directory: ./
File: tasks/ovchinnikov_m_shell_sort_batcher_merge_seq/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 83 85 97.6%
Functions: 12 12 100.0%
Branches: 58 78 74.4%
Line Branch Exec Source
1 #include "ovchinnikov_m_shell_sort_batcher_merge_seq/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <limits>
6 #include <utility>
7 #include <vector>
8
9 #include "ovchinnikov_m_shell_sort_batcher_merge_seq/common/include/common.hpp"
10
11 namespace ovchinnikov_m_shell_sort_batcher_merge_seq {
12
13 namespace {
14
15 std::size_t NextPowerOfTwo(std::size_t value) {
16 std::size_t power = 1;
17
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 48 times.
 168 while (power < value) {
18 120 power <<= 1;
19 }
20 return power;
21 }
22
23 88 std::vector<int> MergeSorted(const std::vector<int> &first, const std::vector<int> &second) {
24
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 std::vector<int> merged;
25
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 merged.reserve(first.size() + second.size());
26
27 std::size_t left_index = 0;
28 std::size_t right_index = 0;
29
4/4
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 64 times.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 176 times.
 264 while (left_index < first.size() && right_index < second.size()) {
30
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 48 times.
 176 if (first[left_index] <= second[right_index]) {
31 merged.push_back(first[left_index]);
32 128 ++left_index;
33 } else {
34 merged.push_back(second[right_index]);
35 48 ++right_index;
36 }
37 }
38
39
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 88 times.
 112 while (left_index < first.size()) {
40 merged.push_back(first[left_index]);
41 24 ++left_index;
42 }
43
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 88 times.
 192 while (right_index < second.size()) {
44 merged.push_back(second[right_index]);
45 104 ++right_index;
46 }
47
48 88 return merged;
49 }
50
51 bool IsEvenPosition(std::size_t index) {
52 576 return (index % 2) == 0;
53 }
54
55 80 void SplitByParity(const std::vector<int> &input, std::vector<int> &even, std::vector<int> &odd) {
56 80 even.reserve((input.size() + 1) / 2);
57 80 odd.reserve(input.size() / 2);
58
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 80 times.
 368 for (std::size_t i = 0; i < input.size(); ++i) {
59
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 144 times.
 288 if (IsEvenPosition(i)) {
60 even.push_back(input[i]);
61 } else {
62 odd.push_back(input[i]);
63 }
64 }
65 80 }
66
67 40 std::vector<int> InterleaveByParity(const std::vector<int> &even, const std::vector<int> &odd) {
68 40 std::vector<int> merged(even.size() + odd.size());
69 std::size_t even_index = 0;
70 std::size_t odd_index = 0;
71
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 40 times.
 328 for (std::size_t i = 0; i < merged.size(); ++i) {
72
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 144 times.
 288 if (IsEvenPosition(i)) {
73 144 merged[i] = even[even_index];
74 144 ++even_index;
75 } else {
76 144 merged[i] = odd[odd_index];
77 144 ++odd_index;
78 }
79 }
80 40 return merged;
81 }
82
83 48 std::pair<std::vector<int>, std::vector<int>> SplitInHalf(const std::vector<int> &data) {
84 48 const auto middle = data.begin() + static_cast<std::ptrdiff_t>(data.size() / 2);
85
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 std::vector<int> left(data.begin(), middle);
86
1/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 48 std::vector<int> right(middle, data.end());
87 48 return {std::move(left), std::move(right)};
88 }
89
90 40 void CompareExchangeOddPairs(std::vector<int> &data) {
91
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 40 times.
 144 for (std::size_t i = 1; i + 1 < data.size(); i += 2) {
92
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 80 times.
 104 if (data[i] > data[i + 1]) {
93 std::swap(data[i], data[i + 1]);
94 }
95 }
96 40 }
97
98 } // namespace
99
100
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 OvchinnikovMShellSortBatcherMergeSEQ::OvchinnikovMShellSortBatcherMergeSEQ(const InType &in) {
101 SetTypeOfTask(GetStaticTypeOfTask());
102
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 GetInput() = in;
103 64 }
104
105 96 void OvchinnikovMShellSortBatcherMergeSEQ::ShellSort(std::vector<int> &data) {
106 const std::size_t n = data.size();
107
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 96 times.
 240 for (std::size_t gap = n / 2; gap > 0; gap /= 2) {
108
2/2
✓ Branch 0 taken 336 times.
✓ Branch 1 taken 144 times.
 480 for (std::size_t i = gap; i < n; ++i) {
109 336 int temp = data[i];
110 std::size_t j = i;
111
4/4
✓ Branch 0 taken 392 times.
✓ Branch 1 taken 72 times.
✓ Branch 2 taken 128 times.
✓ Branch 3 taken 264 times.
 464 while (j >= gap && data[j - gap] > temp) {
112 128 data[j] = data[j - gap];
113 j -= gap;
114 }
115 336 data[j] = temp;
116 }
117 }
118 96 }
119
120
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 std::vector<int> OvchinnikovMShellSortBatcherMergeSEQ::BatcherOddEvenMerge(const std::vector<int> &left,
121 const std::vector<int> &right) {
122
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (left.empty()) {
123 ✗ return right;
124 }
125
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if (right.empty()) {
126 ✗ return left;
127 }
128
129
3/4
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 40 times.
 48 if (left.size() != right.size() || left.size() <= 1) {
130 8 return MergeSorted(left, right);
131 }
132
133 40 std::vector<int> left_even;
134 40 std::vector<int> left_odd;
135 40 std::vector<int> right_even;
136 40 std::vector<int> right_odd;
137
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 SplitByParity(left, left_even, left_odd);
138
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 SplitByParity(right, right_even, right_odd);
139
140
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<int> merged_even = MergeSorted(left_even, right_even);
141
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<int> merged_odd = MergeSorted(left_odd, right_odd);
142
143
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 std::vector<int> merged = InterleaveByParity(merged_even, merged_odd);
144 40 CompareExchangeOddPairs(merged);
145
146 return merged;
147 }
148
149 64 bool OvchinnikovMShellSortBatcherMergeSEQ::ValidationImpl() {
150 64 return true;
151 }
152
153 64 bool OvchinnikovMShellSortBatcherMergeSEQ::PreProcessingImpl() {
154 64 data_ = GetInput();
155 64 return true;
156 }
157
158
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 bool OvchinnikovMShellSortBatcherMergeSEQ::RunImpl() {
159 constexpr std::size_t kMinSizeToSort = 2;
160
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 16 times.
 64 if (data_.size() < kMinSizeToSort) {
161 return true;
162 }
163
164 const std::size_t original_size = data_.size();
165 const std::size_t padded_size = NextPowerOfTwo(original_size);
166 48 data_.resize(padded_size, std::numeric_limits<int>::max());
167
168 48 auto [left, right] = SplitInHalf(data_);
169
170 48 ShellSort(left);
171 48 ShellSort(right);
172
173
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 data_ = BatcherOddEvenMerge(left, right);
174
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 data_.resize(original_size);
175 return true;
176 48 }
177
178
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 8 times.
 64 bool OvchinnikovMShellSortBatcherMergeSEQ::PostProcessingImpl() {
179
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if (!std::ranges::is_sorted(data_.begin(), data_.end())) {
180 return false;
181 }
182 64 GetOutput() = data_;
183 64 return true;
184 }
185
186 } // namespace ovchinnikov_m_shell_sort_batcher_merge_seq
187