GCC Code Coverage Report

Directory: ./
File: tasks/olesnitskiy_v_hoare_sort_simple_merge_seq/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 41 61 67.2%
Functions: 7 8 87.5%
Branches: 28 70 40.0%
Line Branch Exec Source
1 #include "olesnitskiy_v_hoare_sort_simple_merge_seq/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <stack>
6 #include <utility>
7 #include <vector>
8
9 #include "olesnitskiy_v_hoare_sort_simple_merge_seq/common/include/common.hpp"
10
11 namespace olesnitskiy_v_hoare_sort_simple_merge_seq {
12
13
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 OlesnitskiyVHoareSortSimpleMergeSEQ::OlesnitskiyVHoareSortSimpleMergeSEQ(const InType &in) {
14 SetTypeOfTask(GetStaticTypeOfTask());
15
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 GetInput() = in;
16 GetOutput() = {};
17 64 }
18
19 296 int OlesnitskiyVHoareSortSimpleMergeSEQ::HoarePartition(std::vector<int> &array, int left, int right) {
20 296 int pivot = array[left + ((right - left) / 2)];
21 296 int i = left - 1;
22 296 int j = right + 1;
23
24 while (true) {
25 536 i++;
26
2/2
✓ Branch 0 taken 208 times.
✓ Branch 1 taken 536 times.
 744 while (array[i] < pivot) {
27 208 i++;
28 }
29
30 536 j--;
31
2/2
✓ Branch 0 taken 224 times.
✓ Branch 1 taken 536 times.
 760 while (array[j] > pivot) {
32 224 j--;
33 }
34
35
2/2
✓ Branch 0 taken 296 times.
✓ Branch 1 taken 240 times.
 536 if (i >= j) {
36 296 return j;
37 }
38
39 std::swap(array[i], array[j]);
40 }
41 }
42
43 56 void OlesnitskiyVHoareSortSimpleMergeSEQ::HoareQuickSort(std::vector<int> &array, int left, int right) {
44 std::stack<std::pair<int, int>> stack;
45 stack.emplace(left, right);
46
47
2/2
✓ Branch 0 taken 648 times.
✓ Branch 1 taken 56 times.
 704 while (!stack.empty()) {
48 auto [current_left, current_right] = stack.top();
49 stack.pop();
50
51
2/2
✓ Branch 0 taken 352 times.
✓ Branch 1 taken 296 times.
 648 if (current_left >= current_right) {
52 352 continue;
53 }
54
55 296 int middle = HoarePartition(array, current_left, current_right);
56
57
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 192 times.
 296 if ((middle - current_left) > (current_right - (middle + 1))) {
58 stack.emplace(current_left, middle);
59
1/2
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
 104 stack.emplace(middle + 1, current_right);
60 } else {
61
2/4
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 192 times.
✗ Branch 5 not taken.
 192 stack.emplace(middle + 1, current_right);
62 stack.emplace(current_left, middle);
63 }
64 }
65 56 }
66
67 ✗ std::vector<int> OlesnitskiyVHoareSortSimpleMergeSEQ::SimpleMerge(const std::vector<int> &left_part,
68 const std::vector<int> &right_part) {
69 ✗ std::vector<int> result;
70 ✗ result.reserve(left_part.size() + right_part.size());
71
72 size_t left_index = 0;
73 size_t right_index = 0;
74
75 ✗ while (left_index < left_part.size() && right_index < right_part.size()) {
76 ✗ if (left_part[left_index] <= right_part[right_index]) {
77 result.push_back(left_part[left_index]);
78 ✗ left_index++;
79 } else {
80 result.push_back(right_part[right_index]);
81 ✗ right_index++;
82 }
83 }
84
85 ✗ while (left_index < left_part.size()) {
86 result.push_back(left_part[left_index]);
87 ✗ left_index++;
88 }
89
90 ✗ while (right_index < right_part.size()) {
91 result.push_back(right_part[right_index]);
92 ✗ right_index++;
93 }
94
95 ✗ return result;
96 }
97
98 64 bool OlesnitskiyVHoareSortSimpleMergeSEQ::ValidationImpl() {
99 64 return !GetInput().empty();
100 }
101
102 64 bool OlesnitskiyVHoareSortSimpleMergeSEQ::PreProcessingImpl() {
103 64 data_ = GetInput();
104 GetOutput().clear();
105 64 return true;
106 }
107
108
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 8 times.
 64 bool OlesnitskiyVHoareSortSimpleMergeSEQ::RunImpl() {
109
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 8 times.
 64 if (data_.size() <= 1) {
110 return true;
111 }
112
113 constexpr size_t kBlockSize = 64;
114 56 const size_t size = data_.size();
115
116
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 56 times.
 112 for (size_t block_start = 0; block_start < size; block_start += kBlockSize) {
117
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 size_t block_end = std::min(block_start + kBlockSize, size);
118
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if ((block_end - block_start) > 1) {
119 56 HoareQuickSort(data_, static_cast<int>(block_start), static_cast<int>(block_end - 1));
120 }
121 }
122
123
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 for (size_t merge_width = kBlockSize; merge_width < size; merge_width *= 2) {
124 ✗ std::vector<int> merged_data(size);
125
126 ✗ for (size_t left = 0; left < size; left += (2 * merge_width)) {
127 ✗ size_t middle = std::min(left + merge_width, size);
128 ✗ size_t right = std::min(left + (2 * merge_width), size);
129
130 ✗ if (middle < right) {
131 std::vector<int> left_part(data_.begin() + static_cast<std::ptrdiff_t>(left),
132 ✗ data_.begin() + static_cast<std::ptrdiff_t>(middle));
133 std::vector<int> right_part(data_.begin() + static_cast<std::ptrdiff_t>(middle),
134 ✗ data_.begin() + static_cast<std::ptrdiff_t>(right));
135 ✗ std::vector<int> merged_part = SimpleMerge(left_part, right_part);
136 std::ranges::copy(merged_part, merged_data.begin() + static_cast<std::ptrdiff_t>(left));
137 } else {
138 std::ranges::copy(data_.begin() + static_cast<std::ptrdiff_t>(left),
139 data_.begin() + static_cast<std::ptrdiff_t>(right),
140 merged_data.begin() + static_cast<std::ptrdiff_t>(left));
141 }
142 }
143
144 data_.swap(merged_data);
145 }
146
147 return true;
148 }
149
150
1/2
✓ Branch 0 taken 64 times.
✗ Branch 1 not taken.
 64 bool OlesnitskiyVHoareSortSimpleMergeSEQ::PostProcessingImpl() {
151
1/2
✓ Branch 0 taken 64 times.
✗ Branch 1 not taken.
 64 if (!std::ranges::is_sorted(data_)) {
152 return false;
153 }
154 64 GetOutput() = data_;
155 64 return true;
156 }
157
158 } // namespace olesnitskiy_v_hoare_sort_simple_merge_seq
159