GCC Code Coverage Report

Directory: ./
File: tasks/sakharov_a_shell_sorting_with_merging_butcher/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 71 71 100.0%
Functions: 11 11 100.0%
Branches: 54 72 75.0%
Line Branch Exec Source
1 #include "sakharov_a_shell_sorting_with_merging_butcher/seq/include/ops_seq.hpp"
2
3 #include <cstddef>
4 #include <utility>
5 #include <vector>
6
7 #include "sakharov_a_shell_sorting_with_merging_butcher/common/include/common.hpp"
8
9 namespace sakharov_a_shell_sorting_with_merging_butcher {
10
11 namespace {
12
13 64 void SplitByParity(const std::vector<int> &source, std::vector<int> &even, std::vector<int> &odd) {
14 64 even.reserve((source.size() + 1) / 2);
15 64 odd.reserve(source.size() / 2);
16
17
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 64 times.
 240 for (std::size_t index = 0; index < source.size(); ++index) {
18
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 72 times.
 176 if (index % 2 == 0) {
19 even.push_back(source[index]);
20 } else {
21 odd.push_back(source[index]);
22 }
23 }
24 64 }
25
26 32 std::vector<int> Interleave(const std::vector<int> &even, const std::vector<int> &odd) {
27
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 std::vector<int> result;
28
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 result.reserve(even.size() + odd.size());
29
30 std::size_t even_index = 0;
31 std::size_t odd_index = 0;
32
33
3/4
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 32 times.
 136 while (even_index < even.size() || odd_index < odd.size()) {
34
1/2
✓ Branch 0 taken 104 times.
✗ Branch 1 not taken.
 104 if (even_index < even.size()) {
35 result.push_back(even[even_index]);
36 104 ++even_index;
37 }
38
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 32 times.
 104 if (odd_index < odd.size()) {
39 result.push_back(odd[odd_index]);
40 72 ++odd_index;
41 }
42 }
43
44 32 return result;
45 }
46
47 32 void FixOddEvenAdjacents(std::vector<int> &data) {
48
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 32 times.
 96 for (std::size_t index = 1; index + 1 < data.size(); index += 2) {
49
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 32 times.
 64 if (data[index] > data[index + 1]) {
50 std::swap(data[index], data[index + 1]);
51 }
52 }
53 32 }
54
55 } // namespace
56
57
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 SakharovAShellButcherSEQ::SakharovAShellButcherSEQ(const InType &in) {
58 SetTypeOfTask(GetStaticTypeOfTask());
59
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 GetInput() = in;
60 40 }
61
62 40 bool SakharovAShellButcherSEQ::ValidationImpl() {
63 40 return IsValidInput(GetInput());
64 }
65
66 40 bool SakharovAShellButcherSEQ::PreProcessingImpl() {
67 40 GetOutput().assign(GetInput().size(), 0);
68 40 return true;
69 }
70
71
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 void SakharovAShellButcherSEQ::ShellSort(std::vector<int> &data) {
72
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 8 times.
 96 if (data.empty()) {
73 return;
74 }
75
76
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 88 times.
 216 for (std::size_t gap = data.size() / 2; gap > 0; gap /= 2) {
77
2/2
✓ Branch 0 taken 448 times.
✓ Branch 1 taken 128 times.
 576 for (std::size_t i = gap; i < data.size(); ++i) {
78 448 int temp = data[i];
79 std::size_t j = i;
80
4/4
✓ Branch 0 taken 488 times.
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 72 times.
✓ Branch 3 taken 416 times.
 520 while (j >= gap && data[j - gap] > temp) {
81 72 data[j] = data[j - gap];
82 j -= gap;
83 }
84 448 data[j] = temp;
85 }
86 }
87 }
88
89 64 std::vector<int> SakharovAShellButcherSEQ::MergeSortedVectors(const std::vector<int> &left,
90 const std::vector<int> &right) {
91
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 std::vector<int> merged;
92
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 merged.reserve(left.size() + right.size());
93
94 std::size_t left_index = 0;
95 std::size_t right_index = 0;
96
97
4/4
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 40 times.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 112 times.
 176 while (left_index < left.size() && right_index < right.size()) {
98
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 56 times.
 112 if (left[left_index] <= right[right_index]) {
99 merged.push_back(left[left_index]);
100 56 ++left_index;
101 } else {
102 merged.push_back(right[right_index]);
103 56 ++right_index;
104 }
105 }
106
107
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 64 times.
 88 while (left_index < left.size()) {
108 merged.push_back(left[left_index]);
109 24 ++left_index;
110 }
111
112
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 64 times.
 104 while (right_index < right.size()) {
113 merged.push_back(right[right_index]);
114 40 ++right_index;
115 }
116
117 64 return merged;
118 }
119
120 32 std::vector<int> SakharovAShellButcherSEQ::BatcherOddEvenMerge(const std::vector<int> &left,
121 const std::vector<int> &right) {
122 32 std::vector<int> left_even;
123 32 std::vector<int> left_odd;
124 32 std::vector<int> right_even;
125 32 std::vector<int> right_odd;
126
127
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 SplitByParity(left, left_even, left_odd);
128
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 SplitByParity(right, right_even, right_odd);
129
130
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 std::vector<int> even_merged = MergeSortedVectors(left_even, right_even);
131
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 std::vector<int> odd_merged = MergeSortedVectors(left_odd, right_odd);
132
133
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 std::vector<int> result = Interleave(even_merged, odd_merged);
134 32 FixOddEvenAdjacents(result);
135
136 32 return result;
137 }
138
139
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 32 times.
 40 bool SakharovAShellButcherSEQ::RunImpl() {
140 const auto &input = GetInput();
141
142
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 32 times.
 40 if (input.empty()) {
143 GetOutput().clear();
144 8 return true;
145 }
146
147 32 const std::size_t middle = input.size() / 2;
148
149
1/2
✓ Branch 2 taken 32 times.
✗ Branch 3 not taken.
 32 std::vector<int> left(input.begin(), input.begin() + static_cast<std::ptrdiff_t>(middle));
150
1/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 32 std::vector<int> right(input.begin() + static_cast<std::ptrdiff_t>(middle), input.end());
151
152 32 ShellSort(left);
153 32 ShellSort(right);
154
155
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 auto output = BatcherOddEvenMerge(left, right);
156 32 ShellSort(output);
157 GetOutput() = std::move(output);
158 return true;
159 }
160
161 40 bool SakharovAShellButcherSEQ::PostProcessingImpl() {
162 40 return true;
163 }
164
165 } // namespace sakharov_a_shell_sorting_with_merging_butcher
166