GCC Code Coverage Report

Directory: ./
File: tasks/sinev_a_quicksort_with_simple_merge/seq/src/ops_seq.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 69 71 97.2%
Functions: 8 8 100.0%
Branches: 45 58 77.6%
Line Branch Exec Source
1 #include "sinev_a_quicksort_with_simple_merge/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <stack>
5 #include <vector>
6
7 #include "sinev_a_quicksort_with_simple_merge/common/include/common.hpp"
8 // #include "util/include/util.hpp"
9
10 namespace sinev_a_quicksort_with_simple_merge {
11
12
1/2
✓ Branch 1 taken 114 times.
✗ Branch 2 not taken.
 114 SinevAQuicksortWithSimpleMergeSEQ::SinevAQuicksortWithSimpleMergeSEQ(const InType &in) {
13 SetTypeOfTask(GetStaticTypeOfTask());
14
1/2
✓ Branch 1 taken 114 times.
✗ Branch 2 not taken.
 114 GetInput() = in;
15
1/2
✓ Branch 1 taken 114 times.
✗ Branch 2 not taken.
 114 GetOutput().resize(in.size());
16 114 }
17
18 114 bool SinevAQuicksortWithSimpleMergeSEQ::ValidationImpl() {
19 114 return !GetInput().empty();
20 }
21
22 114 bool SinevAQuicksortWithSimpleMergeSEQ::PreProcessingImpl() {
23 114 GetOutput() = GetInput();
24 114 return true;
25 }
26
27 400 int SinevAQuicksortWithSimpleMergeSEQ::Partition(std::vector<int> &arr, int left, int right) {
28 400 int pivot_index = left + ((right - left) / 2);
29 400 int pivot_value = arr[pivot_index];
30
31 400 std::swap(arr[pivot_index], arr[left]);
32
33 400 int i = left + 1;
34 int j = right;
35
36
2/2
✓ Branch 0 taken 528 times.
✓ Branch 1 taken 48 times.
 576 while (i <= j) {
37
4/4
✓ Branch 0 taken 836 times.
✓ Branch 1 taken 136 times.
✓ Branch 2 taken 392 times.
✓ Branch 3 taken 444 times.
 972 while (i <= j && arr[i] <= pivot_value) {
38 444 i++;
39 }
40
41
4/4
✓ Branch 0 taken 608 times.
✓ Branch 1 taken 352 times.
✓ Branch 2 taken 176 times.
✓ Branch 3 taken 432 times.
 960 while (i <= j && arr[j] > pivot_value) {
42 432 j--;
43 }
44
45
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 352 times.
 528 if (i < j) {
46 176 std::swap(arr[i], arr[j]);
47 176 i++;
48 176 j--;
49 } else {
50 break;
51 }
52 }
53
54 400 std::swap(arr[left], arr[j]);
55
56 400 return j;
57 }
58
59 400 void SinevAQuicksortWithSimpleMergeSEQ::SimpleMerge(std::vector<int> &arr, int left, int mid, int right) {
60 400 std::vector<int> temp(right - left + 1);
61
62 int i = left;
63 400 int j = mid + 1;
64 int k = 0; // Индекс для временного массива
65
66
2/2
✓ Branch 0 taken 728 times.
✓ Branch 1 taken 400 times.
 1128 while (i <= mid && j <= right) {
67
1/2
✓ Branch 0 taken 728 times.
✗ Branch 1 not taken.
 728 if (arr[i] <= arr[j]) {
68 728 temp[k] = arr[i];
69 728 i++;
70 } else {
71 ✗ temp[k] = arr[j];
72 ✗ j++;
73 }
74 728 k++;
75 }
76
77
2/2
✓ Branch 0 taken 292 times.
✓ Branch 1 taken 400 times.
 692 while (i <= mid) {
78 292 temp[k] = arr[i];
79 292 i++;
80 292 k++;
81 }
82
83
2/2
✓ Branch 0 taken 608 times.
✓ Branch 1 taken 400 times.
 1008 while (j <= right) {
84 608 temp[k] = arr[j];
85 608 j++;
86 608 k++;
87 }
88
89
2/2
✓ Branch 0 taken 1628 times.
✓ Branch 1 taken 400 times.
 2028 for (int idx = 0; idx < k; idx++) {
90 1628 arr[left + idx] = temp[idx];
91 }
92 400 }
93
94 114 void SinevAQuicksortWithSimpleMergeSEQ::QuickSortWithSimpleMerge(std::vector<int> &arr, int left, int right) {
95 struct Range {
96 int left;
97 int right;
98 };
99
100 std::stack<Range> stack;
101
1/2
✓ Branch 1 taken 114 times.
✗ Branch 2 not taken.
 114 stack.push({left, right});
102
103
2/2
✓ Branch 0 taken 408 times.
✓ Branch 1 taken 114 times.
 522 while (!stack.empty()) {
104
1/2
✓ Branch 0 taken 408 times.
✗ Branch 1 not taken.
 408 Range current = stack.top();
105 stack.pop();
106
107 int l = current.left;
108 int r = current.right;
109
110
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 400 times.
 408 if (l >= r) {
111 continue;
112 }
113
114 400 int pivot_index = Partition(arr, l, r);
115
116 400 int left_size = pivot_index - l;
117 400 int right_size = r - pivot_index;
118
119
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 336 times.
 400 if (left_size > 1 && right_size > 1) {
120
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 40 times.
 64 if (left_size > right_size) {
121
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 stack.push({pivot_index + 1, r});
122
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 48 stack.push({l, pivot_index - 1});
123 } else {
124
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 stack.push({l, pivot_index - 1});
125
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 80 stack.push({pivot_index + 1, r});
126 }
127
2/2
✓ Branch 0 taken 78 times.
✓ Branch 1 taken 258 times.
 336 } else if (left_size > 1) {
128
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 156 stack.push({l, pivot_index - 1});
129
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 170 times.
 258 } else if (right_size > 1) {
130
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 176 stack.push({pivot_index + 1, r});
131 }
132
133 // Выполняем слияние
134
1/2
✓ Branch 1 taken 400 times.
✗ Branch 2 not taken.
 400 SimpleMerge(arr, l, pivot_index, r);
135 }
136 114 }
137
138 114 bool SinevAQuicksortWithSimpleMergeSEQ::RunImpl() {
139 114 QuickSortWithSimpleMerge(GetOutput(), 0, static_cast<int>(GetOutput().size()) - 1);
140
141 114 return true;
142 }
143
144 114 bool SinevAQuicksortWithSimpleMergeSEQ::PostProcessingImpl() {
145 114 return true;
146 }
147
148 } // namespace sinev_a_quicksort_with_simple_merge
149