| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <algorithm> | ||
| 4 | #include <cstring> | ||
| 5 | #include <ctime> | ||
| 6 | #include <utility> | ||
| 7 | #include <vector> | ||
| 8 | |||
| 9 | #include "task/include/task.hpp" | ||
| 10 | |||
| 11 | namespace zavyalov_a_qsort_simple_merge { | ||
| 12 | using InType = std::vector<double>; // сортируемый массив | ||
| 13 | using OutType = std::vector<double>; // результат сортировки | ||
| 14 | using TestType = size_t; // размер массива | ||
| 15 | using BaseTask = ppc::task::Task<InType, OutType>; | ||
| 16 | |||
| 17 | 29163 | inline void InnerCycle(double *mem, int &l, int &r, double piv) { | |
| 18 |
2/2✓ Branch 0 taken 27803 times.
✓ Branch 1 taken 29163 times.
|
56966 | while (mem[l] < piv) { |
| 19 | 27803 | ++l; | |
| 20 | } | ||
| 21 |
2/2✓ Branch 0 taken 31501 times.
✓ Branch 1 taken 29163 times.
|
60664 | while (mem[r] > piv) { |
| 22 | 31501 | --r; | |
| 23 | } | ||
| 24 |
2/2✓ Branch 0 taken 27351 times.
✓ Branch 1 taken 1812 times.
|
29163 | if (l <= r) { |
| 25 | 27351 | std::swap(mem[l++], mem[r--]); | |
| 26 | } | ||
| 27 | 29163 | } | |
| 28 | |||
| 29 | 120 | inline void MyQsort(double *mem, int left, int right) { | |
| 30 |
4/4✓ Branch 0 taken 119 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 107 times.
|
120 | if (mem == nullptr || left >= right) { |
| 31 | 13 | return; | |
| 32 | } | ||
| 33 | |||
| 34 | 107 | std::vector<std::pair<int, int>> stack; | |
| 35 |
1/2✓ Branch 1 taken 107 times.
✗ Branch 2 not taken.
|
107 | stack.emplace_back(left, right); |
| 36 | |||
| 37 |
2/2✓ Branch 0 taken 8553 times.
✓ Branch 1 taken 107 times.
|
8660 | while (!stack.empty()) { |
| 38 | auto [cur_l, cur_r] = stack.back(); | ||
| 39 | stack.pop_back(); | ||
| 40 | |||
| 41 | 8553 | int l = cur_l; | |
| 42 | 8553 | int r = cur_r; | |
| 43 | |||
| 44 | 8553 | int pivot_ind = (l + r) / 2; | |
| 45 | 8553 | double piv = mem[pivot_ind]; | |
| 46 | |||
| 47 |
2/2✓ Branch 0 taken 29163 times.
✓ Branch 1 taken 8553 times.
|
37716 | while (l <= r) { |
| 48 | 29163 | InnerCycle(mem, l, r, piv); | |
| 49 | } | ||
| 50 | |||
| 51 |
2/2✓ Branch 0 taken 4206 times.
✓ Branch 1 taken 4347 times.
|
8553 | if (cur_l < r) { |
| 52 |
1/2✓ Branch 1 taken 4206 times.
✗ Branch 2 not taken.
|
4206 | stack.emplace_back(cur_l, r); |
| 53 | } | ||
| 54 |
2/2✓ Branch 0 taken 4240 times.
✓ Branch 1 taken 4313 times.
|
8553 | if (l < cur_r) { |
| 55 |
1/2✓ Branch 1 taken 4240 times.
✗ Branch 2 not taken.
|
4240 | stack.emplace_back(l, cur_r); |
| 56 | } | ||
| 57 | } | ||
| 58 | } | ||
| 59 | |||
| 60 | } // namespace zavyalov_a_qsort_simple_merge | ||
| 61 |