| 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 krymova_k_quick_sort_simple_merge { | ||
| 12 | using InType = std::vector<int>; | ||
| 13 | using OutType = std::vector<int>; | ||
| 14 | using TestType = std::tuple<int, std::string>; | ||
| 15 | using BaseTask = ppc::task::Task<InType, OutType>; | ||
| 16 | |||
| 17 | 61713 | inline void SortThreeElements(std::vector<int> &arr, int left, int mid, int right) { | |
| 18 |
2/2✓ Branch 0 taken 1776 times.
✓ Branch 1 taken 59937 times.
|
61713 | if (arr[left] > arr[mid]) { |
| 19 | std::swap(arr[left], arr[mid]); | ||
| 20 | } | ||
| 21 |
2/2✓ Branch 0 taken 1298 times.
✓ Branch 1 taken 60415 times.
|
61713 | if (arr[left] > arr[right]) { |
| 22 | std::swap(arr[left], arr[right]); | ||
| 23 | } | ||
| 24 |
2/2✓ Branch 0 taken 2833 times.
✓ Branch 1 taken 58880 times.
|
61713 | if (arr[mid] > arr[right]) { |
| 25 | std::swap(arr[mid], arr[right]); | ||
| 26 | } | ||
| 27 | 61713 | } | |
| 28 | |||
| 29 |
2/2✓ Branch 0 taken 32 times.
✓ Branch 1 taken 195 times.
|
227 | inline void QuickSortIterative(std::vector<int> &arr) { |
| 30 |
2/2✓ Branch 0 taken 32 times.
✓ Branch 1 taken 195 times.
|
227 | if (arr.size() <= 1) { |
| 31 | 32 | return; | |
| 32 | } | ||
| 33 | |||
| 34 | struct StackItem { | ||
| 35 | int left; | ||
| 36 | int right; | ||
| 37 | }; | ||
| 38 | |||
| 39 | 195 | std::vector<StackItem> stack{{0, static_cast<int>(arr.size()) - 1}}; | |
| 40 | |||
| 41 |
2/2✓ Branch 0 taken 123621 times.
✓ Branch 1 taken 195 times.
|
123816 | while (!stack.empty()) { |
| 42 |
2/2✓ Branch 0 taken 61908 times.
✓ Branch 1 taken 61713 times.
|
123621 | const auto [left, right] = stack.back(); |
| 43 | stack.pop_back(); | ||
| 44 | |||
| 45 |
2/2✓ Branch 0 taken 61908 times.
✓ Branch 1 taken 61713 times.
|
123621 | if (left >= right) { |
| 46 | 61908 | continue; | |
| 47 | } | ||
| 48 | |||
| 49 | 61713 | const int mid = left + ((right - left) / 2); | |
| 50 | |||
| 51 | 61713 | SortThreeElements(arr, left, mid, right); | |
| 52 | 61713 | std::swap(arr[mid], arr[right]); | |
| 53 | const int pivot = arr[right]; | ||
| 54 | |||
| 55 | 61713 | int i = left - 1; | |
| 56 |
2/2✓ Branch 0 taken 1742614 times.
✓ Branch 1 taken 61713 times.
|
1804327 | for (int j = left; j < right; ++j) { |
| 57 |
2/2✓ Branch 0 taken 1524981 times.
✓ Branch 1 taken 217633 times.
|
1742614 | if (arr[j] <= pivot) { |
| 58 | 1524981 | ++i; | |
| 59 | 1524981 | std::swap(arr[i], arr[j]); | |
| 60 | } | ||
| 61 | } | ||
| 62 |
2/2✓ Branch 0 taken 57984 times.
✓ Branch 1 taken 3729 times.
|
61713 | std::swap(arr[i + 1], arr[right]); |
| 63 | const int partition = i + 1; | ||
| 64 | |||
| 65 |
2/2✓ Branch 0 taken 57984 times.
✓ Branch 1 taken 3729 times.
|
61713 | if (partition - left > right - partition) { |
| 66 |
1/2✓ Branch 1 taken 57984 times.
✗ Branch 2 not taken.
|
57984 | stack.push_back({left, partition - 1}); |
| 67 |
1/2✓ Branch 1 taken 57984 times.
✗ Branch 2 not taken.
|
57984 | stack.push_back({partition + 1, right}); |
| 68 | } else { | ||
| 69 |
1/2✓ Branch 1 taken 3729 times.
✗ Branch 2 not taken.
|
3729 | stack.push_back({partition + 1, right}); |
| 70 |
1/4✓ Branch 1 taken 3729 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
|
3729 | stack.push_back({left, partition - 1}); |
| 71 | } | ||
| 72 | } | ||
| 73 | } | ||
| 74 | |||
| 75 | } // namespace krymova_k_quick_sort_simple_merge | ||
| 76 |