GCC Code Coverage Report

Directory: ./
File: tasks/yushkova_p_hoare_sorting_simple_merging/omp/src/ops_omp.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 61 61 100.0%
Functions: 8 8 100.0%
Branches: 48 62 77.4%
Line Branch Exec Source
1 #include "yushkova_p_hoare_sorting_simple_merging/omp/include/ops_omp.hpp"
2
3 #include <omp.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <stack>
8 #include <utility>
9 #include <vector>
10
11 #include "yushkova_p_hoare_sorting_simple_merging/common/include/common.hpp"
12
13 namespace yushkova_p_hoare_sorting_simple_merging {
14
15
1/2
✓ Branch 1 taken 68 times.
✗ Branch 2 not taken.
 68 YushkovaPHoareSortingSimpleMergingOMP::YushkovaPHoareSortingSimpleMergingOMP(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 68 times.
✗ Branch 2 not taken.
 68 GetInput() = in;
18 GetOutput().clear();
19 68 }
20
21 2667 int YushkovaPHoareSortingSimpleMergingOMP::HoarePartition(std::vector<int> &values, int left, int right) {
22 2667 const int pivot = values[left + ((right - left) / 2)];
23 2667 int i = left - 1;
24 2667 int j = right + 1;
25
26 while (true) {
27 5106 ++i;
28
2/2
✓ Branch 0 taken 3207 times.
✓ Branch 1 taken 5106 times.
 8313 while (values[i] < pivot) {
29 3207 ++i;
30 }
31
32 5106 --j;
33
2/2
✓ Branch 0 taken 4849 times.
✓ Branch 1 taken 5106 times.
 9955 while (values[j] > pivot) {
34 4849 --j;
35 }
36
37
2/2
✓ Branch 0 taken 2667 times.
✓ Branch 1 taken 2439 times.
 5106 if (i >= j) {
38 2667 return j;
39 }
40
41 std::swap(values[i], values[j]);
42 }
43 }
44
45 138 void YushkovaPHoareSortingSimpleMergingOMP::HoareQuickSort(std::vector<int> &values, int left, int right) {
46 std::stack<std::pair<int, int>> ranges;
47 ranges.emplace(left, right);
48
49
2/2
✓ Branch 0 taken 5472 times.
✓ Branch 1 taken 138 times.
 5610 while (!ranges.empty()) {
50 auto [current_left, current_right] = ranges.top();
51 ranges.pop();
52
53
2/2
✓ Branch 0 taken 2805 times.
✓ Branch 1 taken 2667 times.
 5472 if (current_left >= current_right) {
54 2805 continue;
55 }
56
57 2667 const int partition_index = HoarePartition(values, current_left, current_right);
58
59
2/2
✓ Branch 0 taken 487 times.
✓ Branch 1 taken 2180 times.
 2667 if ((partition_index - current_left) > (current_right - (partition_index + 1))) {
60 ranges.emplace(current_left, partition_index);
61
1/2
✓ Branch 1 taken 487 times.
✗ Branch 2 not taken.
 487 ranges.emplace(partition_index + 1, current_right);
62 } else {
63
2/4
✓ Branch 1 taken 2180 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2180 times.
✗ Branch 5 not taken.
 2180 ranges.emplace(partition_index + 1, current_right);
64 ranges.emplace(current_left, partition_index);
65 }
66 }
67 138 }
68
69 93 void YushkovaPHoareSortingSimpleMergingOMP::Merge(std::vector<int> &values, int left, int mid, int right) {
70 93 std::vector<int> merged;
71 93 const int merged_size = (right - left) + 1;
72
1/2
✓ Branch 1 taken 93 times.
✗ Branch 2 not taken.
 93 merged.reserve(static_cast<std::size_t>(merged_size));
73
74 int left_index = left;
75 93 int right_index = mid + 1;
76
77
2/2
✓ Branch 0 taken 1984 times.
✓ Branch 1 taken 93 times.
 2077 while (left_index <= mid && right_index <= right) {
78
2/2
✓ Branch 0 taken 1043 times.
✓ Branch 1 taken 941 times.
 1984 if (values[left_index] <= values[right_index]) {
79
1/2
✓ Branch 0 taken 1043 times.
✗ Branch 1 not taken.
 1043 merged.push_back(values[left_index++]);
80 } else {
81
1/2
✓ Branch 0 taken 941 times.
✗ Branch 1 not taken.
 941 merged.push_back(values[right_index++]);
82 }
83 }
84
85
2/2
✓ Branch 0 taken 1043 times.
✓ Branch 1 taken 93 times.
 1136 while (left_index <= mid) {
86
1/2
✓ Branch 0 taken 1043 times.
✗ Branch 1 not taken.
 1043 merged.push_back(values[left_index++]);
87 }
88
89
2/2
✓ Branch 0 taken 425 times.
✓ Branch 1 taken 93 times.
 518 while (right_index <= right) {
90
1/2
✓ Branch 0 taken 425 times.
✗ Branch 1 not taken.
 425 merged.push_back(values[right_index++]);
91 }
92
93
2/2
✓ Branch 0 taken 3452 times.
✓ Branch 1 taken 93 times.
 3545 for (std::size_t idx = 0; idx < merged.size(); ++idx) {
94 3452 values[static_cast<std::size_t>(left) + idx] = merged[idx];
95 }
96 93 }
97
98 68 bool YushkovaPHoareSortingSimpleMergingOMP::ValidationImpl() {
99 68 return !GetInput().empty();
100 }
101
102 68 bool YushkovaPHoareSortingSimpleMergingOMP::PreProcessingImpl() {
103 68 GetOutput() = GetInput();
104 68 return true;
105 }
106
107
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 64 times.
 68 bool YushkovaPHoareSortingSimpleMergingOMP::RunImpl() {
108 std::vector<int> &values = GetOutput();
109 68 const int n = static_cast<int>(values.size());
110
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 64 times.
 68 if (n <= 1) {
111 return true;
112 }
113
114
2/2
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 48 times.
 64 const int max_threads = std::max(1, omp_get_max_threads());
115 const int chunks = std::min(max_threads, n);
116
117
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 48 times.
 64 if (chunks == 1) {
118 16 HoareQuickSort(values, 0, n - 1);
119 return std::ranges::is_sorted(values);
120 }
121
122 48 std::vector<int> borders(static_cast<std::size_t>(chunks + 1));
123
2/2
✓ Branch 0 taken 189 times.
✓ Branch 1 taken 48 times.
 237 for (int i = 0; i <= chunks; ++i) {
124 189 borders[static_cast<std::size_t>(i)] = (i * n) / chunks;
125 }
126
127 48 #pragma omp parallel for default(none) shared(values, borders, chunks)
128 for (int chunk = 0; chunk < chunks; ++chunk) {
129 const int left = borders[static_cast<std::size_t>(chunk)];
130 const int right = borders[static_cast<std::size_t>(chunk) + 1] - 1;
131 if (left < right) {
132 HoareQuickSort(values, left, right);
133 }
134 }
135
136
2/2
✓ Branch 0 taken 93 times.
✓ Branch 1 taken 48 times.
 141 for (int i = 0; i < chunks - 1; ++i) {
137
1/2
✓ Branch 1 taken 93 times.
✗ Branch 2 not taken.
 93 const int mid = borders[static_cast<std::size_t>(i) + 1] - 1;
138 93 const int right = borders[static_cast<std::size_t>(i) + 2] - 1;
139
1/2
✓ Branch 1 taken 93 times.
✗ Branch 2 not taken.
 93 Merge(values, 0, mid, right);
140 }
141
142 return std::ranges::is_sorted(values);
143 }
144
145
1/2
✓ Branch 0 taken 68 times.
✗ Branch 1 not taken.
 68 bool YushkovaPHoareSortingSimpleMergingOMP::PostProcessingImpl() {
146
1/2
✓ Branch 0 taken 68 times.
✗ Branch 1 not taken.
 68 return !GetOutput().empty() && std::ranges::is_sorted(GetOutput());
147 }
148
149 } // namespace yushkova_p_hoare_sorting_simple_merging
150