GCC Code Coverage Report

Directory: ./
File: tasks/krasnopevtseva_v_hoare_batcher_sort/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 69 72 95.8%
Functions: 10 11 90.9%
Branches: 53 74 71.6%
Line Branch Exec Source
1 #include "krasnopevtseva_v_hoare_batcher_sort/seq/include/ops_seq.hpp"
2
3 #include <cstddef>
4 #include <functional>
5 #include <stack>
6 #include <utility>
7 #include <vector>
8
9 #include "krasnopevtseva_v_hoare_batcher_sort/common/include/common.hpp"
10
11 namespace krasnopevtseva_v_hoare_batcher_sort {
12
13
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 KrasnopevtsevaVHoareBatcherSortSEQ::KrasnopevtsevaVHoareBatcherSortSEQ(const InType &in) {
14 SetTypeOfTask(GetStaticTypeOfTask());
15
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
16 48 GetOutput() = std::vector<int>();
17 48 }
18
19 48 bool KrasnopevtsevaVHoareBatcherSortSEQ::ValidationImpl() {
20 const auto &input = GetInput();
21 48 return (!input.empty());
22 }
23
24 48 bool KrasnopevtsevaVHoareBatcherSortSEQ::PreProcessingImpl() {
25 48 GetOutput() = std::vector<int>();
26 48 return true;
27 }
28
29 48 bool KrasnopevtsevaVHoareBatcherSortSEQ::RunImpl() {
30 const auto &input = GetInput();
31 size_t size = input.size();
32 48 std::vector<int> sort_v = input;
33
34
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if (size > 1) {
35
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 QuickBatcherSort(sort_v, 0, static_cast<int>(size - 1));
36 }
37
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetOutput() = sort_v;
38 48 return true;
39 }
40
41 ✗ void KrasnopevtsevaVHoareBatcherSortSEQ::CompareAndSwap(int &a, int &b) {
42
2/6
✗ Branch 0 not taken.
✓ Branch 1 taken 200 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 376 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 576 if (a > b) {
43 std::swap(a, b);
44 }
45 ✗ }
46
47 8 void KrasnopevtsevaVHoareBatcherSortSEQ::BatcherMerge(std::vector<int> &arr, int left, int right) {
48 8 int n = right - left + 1;
49
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 if (n <= 1) {
50 ✗ return;
51 }
52
53
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 std::vector<int> temp(arr.begin() + left, arr.begin() + right + 1);
54
55 808 std::function<void(int, int)> odd_even_merge = [&](int l, int r) {
56
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 408 times.
 808 if (l == r) {
57 return;
58 }
59
60 400 int m = l + ((r - l) / 2);
61
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 400 times.
 400 odd_even_merge(l, m);
62
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 400 times.
 400 odd_even_merge(m + 1, r);
63
64
2/2
✓ Branch 0 taken 376 times.
✓ Branch 1 taken 400 times.
 776 for (int i = l + 1; i + (m - l + 1) <= r; i += 2) {
65
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 376 times.
 376 CompareAndSwap(temp[i], temp[i + (m - l + 1)]);
66 }
67 };
68
69 8 odd_even_merge(0, n - 1);
70
71
2/2
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 8 times.
 208 for (int i = 1; i + 1 < n; i += 2) {
72
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 200 times.
 200 CompareAndSwap(temp[i], temp[i + 1]);
73 }
74
2/2
✓ Branch 0 taken 408 times.
✓ Branch 1 taken 8 times.
 416 for (int i = 0; i < n; i++) {
75 408 arr[left + i] = temp[i];
76 }
77 }
78
79 48 void KrasnopevtsevaVHoareBatcherSortSEQ::QuickBatcherSort(std::vector<int> &arr, int left, int right) {
80 std::stack<std::pair<int, int>> stack;
81 stack.emplace(left, right);
82
83
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 48 times.
 192 while (!stack.empty()) {
84 auto [l, r] = stack.top();
85 stack.pop();
86
87
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 144 times.
 144 if (l >= r) {
88 96 continue;
89 }
90
91
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 48 times.
 144 if (r - l < 16) {
92 96 InsertionSort(arr, l, r);
93 96 continue;
94 }
95
96 48 int pivot_index = Partition(arr, l, r);
97
98
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 32 times.
 48 if (pivot_index - l < r - pivot_index) {
99
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 stack.emplace(pivot_index + 1, r);
100
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 stack.emplace(l, pivot_index - 1);
101 } else {
102
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 stack.emplace(l, pivot_index - 1);
103
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 stack.emplace(pivot_index + 1, r);
104 }
105 }
106
107
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 40 times.
 48 if (right - left > 32) {
108
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 BatcherMerge(arr, left, right);
109 }
110 48 }
111
112 96 void KrasnopevtsevaVHoareBatcherSortSEQ::InsertionSort(std::vector<int> &arr, int left, int right) {
113
2/2
✓ Branch 0 taken 848 times.
✓ Branch 1 taken 96 times.
 944 for (int i = left + 1; i <= right; ++i) {
114 848 int key = arr[i];
115 848 int j = i - 1;
116
4/4
✓ Branch 0 taken 2112 times.
✓ Branch 1 taken 104 times.
✓ Branch 2 taken 1368 times.
✓ Branch 3 taken 744 times.
 2216 while (j >= left && arr[j] > key) {
117 1368 arr[j + 1] = arr[j];
118 1368 --j;
119 }
120 848 arr[j + 1] = key;
121 }
122 96 }
123
124 48 int KrasnopevtsevaVHoareBatcherSortSEQ::Partition(std::vector<int> &arr, int left, int right) {
125 48 int mid = left + ((right - left) / 2);
126
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 32 times.
 48 if (arr[left] > arr[mid]) {
127 std::swap(arr[left], arr[mid]);
128 }
129
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 if (arr[left] > arr[right]) {
130 std::swap(arr[left], arr[right]);
131 }
132
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 8 times.
 48 if (arr[mid] > arr[right]) {
133 std::swap(arr[mid], arr[right]);
134 }
135
136 48 std::swap(arr[mid], arr[right - 1]);
137 int pivot = arr[right - 1];
138
139 int i = left;
140 int j = right - 1;
141
142 while (true) {
143
2/2
✓ Branch 0 taken 496 times.
✓ Branch 1 taken 312 times.
 808 while (arr[++i] < pivot) {
144 }
145
2/2
✓ Branch 0 taken 192 times.
✓ Branch 1 taken 312 times.
 504 while (arr[--j] > pivot) {
146 }
147
2/2
✓ Branch 0 taken 264 times.
✓ Branch 1 taken 48 times.
 312 if (i >= j) {
148 break;
149 }
150 std::swap(arr[i], arr[j]);
151 }
152
153 std::swap(arr[i], arr[right - 1]);
154 48 return i;
155 }
156
157 48 bool KrasnopevtsevaVHoareBatcherSortSEQ::PostProcessingImpl() {
158 48 return true;
159 }
160 } // namespace krasnopevtseva_v_hoare_batcher_sort
161