| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <cstddef> | ||
| 4 | #include <utility> | ||
| 5 | #include <vector> | ||
| 6 | |||
| 7 | #include "task/include/task.hpp" | ||
| 8 | |||
| 9 | namespace nikitina_v_quick_sort_merge { | ||
| 10 | |||
| 11 | using InType = std::vector<int>; | ||
| 12 | using OutType = std::vector<int>; | ||
| 13 | using BaseTask = ppc::task::Task<InType, OutType>; | ||
| 14 | |||
| 15 | 2819 | inline std::pair<int, int> Partition(std::vector<int> &vec, int left, int right) { | |
| 16 | int i = left; | ||
| 17 | int j = right; | ||
| 18 | 2819 | int pivot = vec[(left + right) / 2]; | |
| 19 | |||
| 20 |
2/2✓ Branch 0 taken 6053 times.
✓ Branch 1 taken 2819 times.
|
11691 | while (i <= j) { |
| 21 |
2/2✓ Branch 0 taken 5698 times.
✓ Branch 1 taken 6053 times.
|
11751 | while (vec[i] < pivot) { |
| 22 | 5698 | i++; | |
| 23 | } | ||
| 24 |
2/2✓ Branch 0 taken 6303 times.
✓ Branch 1 taken 6053 times.
|
12356 | while (vec[j] > pivot) { |
| 25 | 6303 | j--; | |
| 26 | } | ||
| 27 |
2/2✓ Branch 0 taken 713 times.
✓ Branch 1 taken 5340 times.
|
6053 | if (i <= j) { |
| 28 | std::swap(vec[i], vec[j]); | ||
| 29 | 5340 | i++; | |
| 30 | 5340 | j--; | |
| 31 | } | ||
| 32 | } | ||
| 33 | 2819 | return {i, j}; | |
| 34 | } | ||
| 35 | |||
| 36 | 189 | inline void QuickSortImpl(std::vector<int> &vec, int left, int right) { | |
| 37 |
2/2✓ Branch 0 taken 19 times.
✓ Branch 1 taken 170 times.
|
189 | if (left >= right) { |
| 38 | 19 | return; | |
| 39 | } | ||
| 40 | |||
| 41 | 170 | std::vector<std::pair<int, int>> stack; | |
| 42 |
1/2✓ Branch 1 taken 170 times.
✗ Branch 2 not taken.
|
170 | stack.reserve(static_cast<size_t>(right - left) + 1); |
| 43 |
1/2✓ Branch 1 taken 170 times.
✗ Branch 2 not taken.
|
170 | stack.emplace_back(left, right); |
| 44 | |||
| 45 |
2/2✓ Branch 0 taken 2819 times.
✓ Branch 1 taken 170 times.
|
2989 | while (!stack.empty()) { |
| 46 | auto [l, r] = stack.back(); | ||
| 47 | stack.pop_back(); | ||
| 48 | |||
| 49 | 2819 | auto [i, j] = Partition(vec, l, r); | |
| 50 | |||
| 51 |
2/2✓ Branch 0 taken 1280 times.
✓ Branch 1 taken 1539 times.
|
2819 | if (l < j) { |
| 52 |
1/2✓ Branch 1 taken 1280 times.
✗ Branch 2 not taken.
|
1280 | stack.emplace_back(l, j); |
| 53 | } | ||
| 54 |
2/2✓ Branch 0 taken 1369 times.
✓ Branch 1 taken 1450 times.
|
2819 | if (i < r) { |
| 55 |
1/2✓ Branch 1 taken 1369 times.
✗ Branch 2 not taken.
|
1369 | stack.emplace_back(i, r); |
| 56 | } | ||
| 57 | } | ||
| 58 | } | ||
| 59 | |||
| 60 | } // namespace nikitina_v_quick_sort_merge | ||
| 61 |