GCC Code Coverage Report

Directory: ./
File: tasks/tochilin_e_hoar_sort_sim_mer/seq/src/ops_seq.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 45 45 100.0%
Functions: 8 8 100.0%
Branches: 34 56 60.7%
Line Branch Exec Source
1 #include "tochilin_e_hoar_sort_sim_mer/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <iterator>
5 #include <utility>
6 #include <vector>
7
8 #include "tochilin_e_hoar_sort_sim_mer/common/include/common.hpp"
9
10 namespace tochilin_e_hoar_sort_sim_mer {
11
12
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 TochilinEHoarSortSimMerSEQ::TochilinEHoarSortSimMerSEQ(const InType &in) {
13 SetTypeOfTask(GetStaticTypeOfTask());
14
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 GetInput() = in;
15 80 }
16
17 80 bool TochilinEHoarSortSimMerSEQ::ValidationImpl() {
18 80 return !GetInput().empty();
19 }
20
21 80 bool TochilinEHoarSortSimMerSEQ::PreProcessingImpl() {
22 80 GetOutput() = GetInput();
23 80 return true;
24 }
25
26 26432 std::pair<int, int> TochilinEHoarSortSimMerSEQ::Partition(std::vector<int> &arr, int l, int r) {
27 int i = l;
28 int j = r;
29 26432 int pivot = arr[(l + r) / 2];
30
31
2/2
✓ Branch 0 taken 81104 times.
✓ Branch 1 taken 26432 times.
 133968 while (i <= j) {
32
2/2
✓ Branch 0 taken 100968 times.
✓ Branch 1 taken 81104 times.
 182072 while (arr[i] < pivot) {
33 100968 ++i;
34 }
35
2/2
✓ Branch 0 taken 115272 times.
✓ Branch 1 taken 81104 times.
 196376 while (arr[j] > pivot) {
36 115272 --j;
37 }
38
2/2
✓ Branch 0 taken 7888 times.
✓ Branch 1 taken 73216 times.
 81104 if (i <= j) {
39 std::swap(arr[i], arr[j]);
40 73216 ++i;
41 73216 --j;
42 }
43 }
44 26432 return {i, j};
45 }
46
47 160 void TochilinEHoarSortSimMerSEQ::QuickSort(std::vector<int> &arr, int low, int high) {
48
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 128 times.
 160 if (low >= high) {
49 32 return;
50 }
51
52 128 std::vector<std::pair<int, int>> stack;
53
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 stack.emplace_back(low, high);
54
55
2/2
✓ Branch 0 taken 26432 times.
✓ Branch 1 taken 128 times.
 26560 while (!stack.empty()) {
56 auto [l, r] = stack.back();
57 stack.pop_back();
58
59 26432 auto [i, j] = Partition(arr, l, r);
60
61
2/2
✓ Branch 0 taken 12968 times.
✓ Branch 1 taken 13464 times.
 26432 if (l < j) {
62
1/2
✓ Branch 1 taken 12968 times.
✗ Branch 2 not taken.
 12968 stack.emplace_back(l, j);
63 }
64
2/2
✓ Branch 0 taken 13336 times.
✓ Branch 1 taken 13096 times.
 26432 if (i < r) {
65
1/2
✓ Branch 1 taken 13336 times.
✗ Branch 2 not taken.
 13336 stack.emplace_back(i, r);
66 }
67 }
68 }
69
70 80 std::vector<int> TochilinEHoarSortSimMerSEQ::MergeSortedVectors(const std::vector<int> &a, const std::vector<int> &b) {
71
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 std::vector<int> result;
72
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 result.reserve(a.size() + b.size());
73
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 std::ranges::merge(a, b, std::back_inserter(result));
74 80 return result;
75 }
76
77
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 bool TochilinEHoarSortSimMerSEQ::RunImpl() {
78 auto &data = GetOutput();
79
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 if (data.empty()) {
80 return false;
81 }
82
83 80 const auto mid = static_cast<std::vector<int>::difference_type>(data.size() / 2);
84
85
1/2
✓ Branch 2 taken 80 times.
✗ Branch 3 not taken.
 80 std::vector<int> left(data.begin(), data.begin() + mid);
86
2/6
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 80 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 80 std::vector<int> right(data.begin() + mid, data.end());
87
88
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 QuickSort(left, 0, static_cast<int>(left.size()) - 1);
89
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 QuickSort(right, 0, static_cast<int>(right.size()) - 1);
90
91
2/6
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 80 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 160 data = MergeSortedVectors(left, right);
92
93 return true;
94 }
95
96
1/2
✓ Branch 0 taken 80 times.
✗ Branch 1 not taken.
 80 bool TochilinEHoarSortSimMerSEQ::PostProcessingImpl() {
97 80 return std::is_sorted(GetOutput().begin(), GetOutput().end());
98 }
99
100 } // namespace tochilin_e_hoar_sort_sim_mer
101