| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <algorithm> | ||
| 4 | #include <string> | ||
| 5 | #include <tuple> | ||
| 6 | #include <utility> | ||
| 7 | #include <vector> | ||
| 8 | |||
| 9 | #include "task/include/task.hpp" | ||
| 10 | |||
| 11 | namespace maslova_u_fast_sort_simple { | ||
| 12 | |||
| 13 | using InType = std::vector<int>; | ||
| 14 | using OutType = std::vector<int>; | ||
| 15 | using TestType = std::tuple<InType, OutType, std::string>; | ||
| 16 | using BaseTask = ppc::task::Task<InType, OutType>; | ||
| 17 | |||
| 18 | 654 | inline auto Partition(int *data, int low, int high) { | |
| 19 | 654 | int pivot = data[low + ((high - low) / 2)]; | |
| 20 | int i = low; | ||
| 21 | int j = high; | ||
| 22 |
2/2✓ Branch 0 taken 2887 times.
✓ Branch 1 taken 654 times.
|
4195 | while (i <= j) { |
| 23 |
2/2✓ Branch 0 taken 40 times.
✓ Branch 1 taken 2887 times.
|
2927 | while (data[i] < pivot) { |
| 24 | 40 | i++; | |
| 25 | } | ||
| 26 |
2/2✓ Branch 0 taken 45 times.
✓ Branch 1 taken 2887 times.
|
2932 | while (data[j] > pivot) { |
| 27 | 45 | j--; | |
| 28 | } | ||
| 29 |
2/2✓ Branch 0 taken 16 times.
✓ Branch 1 taken 2871 times.
|
2887 | if (i <= j) { |
| 30 | std::swap(data[i], data[j]); | ||
| 31 | 2871 | i++; | |
| 32 | 2871 | j--; | |
| 33 | } | ||
| 34 | } | ||
| 35 | 654 | return std::make_pair(i, j); | |
| 36 | } | ||
| 37 | |||
| 38 | 654 | inline void PushToStack(std::vector<std::pair<int, int>> *stack, int low, int j, int i, int high) { | |
| 39 |
2/2✓ Branch 0 taken 37 times.
✓ Branch 1 taken 617 times.
|
654 | if ((high - i) > (j - low)) { |
| 40 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 37 times.
|
37 | if (low < j) { |
| 41 | ✗ | stack->emplace_back(low, j); | |
| 42 | } | ||
| 43 |
2/2✓ Branch 0 taken 18 times.
✓ Branch 1 taken 19 times.
|
37 | if (i < high) { |
| 44 | 18 | stack->emplace_back(i, high); | |
| 45 | } | ||
| 46 | } else { | ||
| 47 |
2/2✓ Branch 0 taken 294 times.
✓ Branch 1 taken 323 times.
|
617 | if (i < high) { |
| 48 | 294 | stack->emplace_back(i, high); | |
| 49 | } | ||
| 50 |
2/2✓ Branch 0 taken 302 times.
✓ Branch 1 taken 315 times.
|
617 | if (low < j) { |
| 51 | 302 | stack->emplace_back(low, j); | |
| 52 | } | ||
| 53 | } | ||
| 54 | 654 | } | |
| 55 | |||
| 56 | 49 | inline void QuickSort(int *data, int left, int right) { | |
| 57 |
3/4✓ Branch 0 taken 49 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 9 times.
✓ Branch 3 taken 40 times.
|
49 | if (data == nullptr || left >= right) { |
| 58 | 9 | return; | |
| 59 | } | ||
| 60 | |||
| 61 | 40 | std::vector<std::pair<int, int>> stack; | |
| 62 |
1/2✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
|
40 | stack.reserve(64); |
| 63 |
1/2✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
|
40 | stack.emplace_back(left, right); |
| 64 | |||
| 65 |
2/2✓ Branch 0 taken 654 times.
✓ Branch 1 taken 40 times.
|
694 | while (!stack.empty()) { |
| 66 | auto [low, high] = stack.back(); | ||
| 67 | stack.pop_back(); | ||
| 68 | |||
| 69 | 654 | auto [i, j] = Partition(data, low, high); | |
| 70 |
1/2✓ Branch 1 taken 654 times.
✗ Branch 2 not taken.
|
654 | PushToStack(&stack, low, j, i, high); |
| 71 | } | ||
| 72 | } | ||
| 73 | |||
| 74 | } // namespace maslova_u_fast_sort_simple | ||
| 75 |