GCC Code Coverage Report

Directory: ./
File: tasks/shkrebko_m_shell_sort_batcher_merge/common/include/utils.hpp
Date: 2026-01-10 02:40:41
Exec Total Coverage
Lines: 51 51 100.0%
Functions: 5 5 100.0%
Branches: 52 68 76.5%
Line Branch Exec Source
1 #pragma once
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <vector>
6
7 namespace shkrebko_m_shell_sort_batcher_merge {
8
9 30 inline void ShellSort(std::vector<int> *vec) {
10 auto &a = *vec;
11 const std::size_t n = a.size();
12
2/2
✓ Branch 0 taken 274 times.
✓ Branch 1 taken 30 times.
 304 for (std::size_t gap = n / 2; gap > 0; gap /= 2) {
13
2/2
✓ Branch 0 taken 1145540 times.
✓ Branch 1 taken 274 times.
 1145814 for (std::size_t i = gap; i < n; ++i) {
14 1145540 const int tmp = a[i];
15 std::size_t j = i;
16
4/4
✓ Branch 0 taken 2550606 times.
✓ Branch 1 taken 51434 times.
✓ Branch 2 taken 1456500 times.
✓ Branch 3 taken 1094106 times.
 2602040 while (j >= gap && a[j - gap] > tmp) {
17 1456500 a[j] = a[j - gap];
18 j -= gap;
19 }
20 1145540 a[j] = tmp;
21 }
22 }
23 30 }
24
25 struct Elem {
26 int val{};
27 bool pad{false};
28
29 17536 Elem(int value, bool padding) : val(value), pad(padding) {}
30 };
31
32 inline bool Greater(const Elem &lhs, const Elem &rhs) {
33
2/2
✓ Branch 0 taken 31152 times.
✓ Branch 1 taken 858960 times.
 890112 if (lhs.pad != rhs.pad) {
34
3/4
✓ Branch 0 taken 16628 times.
✓ Branch 1 taken 14524 times.
✓ Branch 2 taken 16628 times.
✗ Branch 3 not taken.
 31152 return lhs.pad && !rhs.pad;
35 }
36 858960 return lhs.val > rhs.val;
37 }
38
39
2/2
✓ Branch 0 taken 31152 times.
✓ Branch 1 taken 858960 times.
 890112 inline void CompareExchange(std::vector<Elem> *arr, std::size_t i, std::size_t j) {
40
2/2
✓ Branch 0 taken 266528 times.
✓ Branch 1 taken 592432 times.
 858960 if (Greater((*arr)[i], (*arr)[j])) {
41 std::swap((*arr)[i], (*arr)[j]);
42 }
43 890112 }
44
45 inline std::size_t NextPow2(std::size_t x) {
46 std::size_t p = 1;
47
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 3 times.
 31 while (p < x) {
48 28 p <<= 1U;
49 }
50 return p;
51 }
52
53 188 inline void OddEvenMergeStep(std::vector<Elem> *arr, std::size_t k, std::size_t j) {
54 const std::size_t n = arr->size();
55
2/2
✓ Branch 0 taken 1780224 times.
✓ Branch 1 taken 188 times.
 1780412 for (std::size_t i = 0; i < n; ++i) {
56 1780224 const std::size_t ixj = i ^ j;
57
2/2
✓ Branch 0 taken 890112 times.
✓ Branch 1 taken 890112 times.
 1780224 if (ixj > i) {
58
2/2
✓ Branch 0 taken 505184 times.
✓ Branch 1 taken 384928 times.
 890112 if ((i & k) == 0) {
59 505184 CompareExchange(arr, i, ixj);
60 } else {
61 384928 CompareExchange(arr, ixj, i);
62 }
63 }
64 }
65 188 }
66
67
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 inline void OddEvenMergeNetwork(std::vector<Elem> *arr) {
68 const std::size_t n = arr->size();
69
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (n <= 1) {
70 return;
71 }
72
73
2/2
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 3 times.
 34 for (std::size_t k = 2; k <= n; k <<= 1U) {
74
2/2
✓ Branch 0 taken 188 times.
✓ Branch 1 taken 31 times.
 219 for (std::size_t j = (k >> 1U); j > 0; j >>= 1U) {
75 188 OddEvenMergeStep(arr, k, j);
76 }
77 }
78 }
79
80
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 inline std::vector<int> BatcherOddEvenMerge(const std::vector<int> &a, const std::vector<int> &b) {
81 3 const std::size_t need = a.size() + b.size();
82
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 const std::size_t half = NextPow2((a.size() > b.size()) ? a.size() : b.size());
83
84 3 std::vector<Elem> buffer;
85
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 buffer.reserve(2 * half);
86
87
2/2
✓ Branch 0 taken 8768 times.
✓ Branch 1 taken 3 times.
 8771 for (std::size_t i = 0; i < half; ++i) {
88
2/2
✓ Branch 0 taken 5550 times.
✓ Branch 1 taken 3218 times.
 8768 if (i < a.size()) {
89
1/2
✓ Branch 1 taken 5550 times.
✗ Branch 2 not taken.
 5550 buffer.emplace_back(a[i], false);
90 } else {
91
1/2
✓ Branch 1 taken 3218 times.
✗ Branch 2 not taken.
 3218 buffer.emplace_back(0, true);
92 }
93 }
94
2/2
✓ Branch 0 taken 8768 times.
✓ Branch 1 taken 3 times.
 8771 for (std::size_t i = 0; i < half; ++i) {
95
2/2
✓ Branch 0 taken 5550 times.
✓ Branch 1 taken 3218 times.
 8768 if (i < b.size()) {
96
1/2
✓ Branch 1 taken 5550 times.
✗ Branch 2 not taken.
 5550 buffer.emplace_back(b[i], false);
97 } else {
98
1/4
✓ Branch 1 taken 3218 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 3218 buffer.emplace_back(0, true);
99 }
100 }
101
102 3 OddEvenMergeNetwork(&buffer);
103
104 3 std::vector<int> out;
105
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 out.reserve(need);
106
1/2
✓ Branch 0 taken 11100 times.
✗ Branch 1 not taken.
 11100 for (const auto &elem : buffer) {
107
1/2
✓ Branch 0 taken 11100 times.
✗ Branch 1 not taken.
 11100 if (!elem.pad) {
108
1/2
✓ Branch 0 taken 11100 times.
✗ Branch 1 not taken.
 11100 out.push_back(elem.val);
109 }
110
2/2
✓ Branch 0 taken 11097 times.
✓ Branch 1 taken 3 times.
 11100 if (out.size() == need) {
111 break;
112 }
113 }
114 3 return out;
115 }
116
117 } // namespace shkrebko_m_shell_sort_batcher_merge
118