| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "dolov_v_qsort_batcher/seq/include/ops_seq.hpp" | ||
| 2 | |||
| 3 | #include <algorithm> | ||
| 4 | #include <stack> | ||
| 5 | #include <utility> | ||
| 6 | #include <vector> | ||
| 7 | |||
| 8 | #include "dolov_v_qsort_batcher/common/include/common.hpp" | ||
| 9 | |||
| 10 | namespace dolov_v_qsort_batcher { | ||
| 11 | |||
| 12 |
1/2✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
|
48 | DolovVQsortBatcherSEQ::DolovVQsortBatcherSEQ(const InType &in) { |
| 13 | SetTypeOfTask(GetStaticTypeOfTask()); | ||
| 14 |
1/2✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
|
48 | GetInput() = in; |
| 15 | 48 | } | |
| 16 | |||
| 17 | 48 | bool DolovVQsortBatcherSEQ::ValidationImpl() { | |
| 18 | 48 | return true; | |
| 19 | } | ||
| 20 | |||
| 21 | 48 | bool DolovVQsortBatcherSEQ::PreProcessingImpl() { | |
| 22 | 48 | res_array_ = GetInput(); | |
| 23 | 48 | return true; | |
| 24 | } | ||
| 25 | |||
| 26 |
2/2✓ Branch 0 taken 40 times.
✓ Branch 1 taken 8 times.
|
48 | bool DolovVQsortBatcherSEQ::RunImpl() { |
| 27 |
2/2✓ Branch 0 taken 40 times.
✓ Branch 1 taken 8 times.
|
48 | if (res_array_.empty()) { |
| 28 | return true; | ||
| 29 | } | ||
| 30 | 40 | ApplyQuicksort(res_array_.data(), 0, static_cast<int>(res_array_.size()) - 1); | |
| 31 | 40 | return true; | |
| 32 | } | ||
| 33 | |||
| 34 | 48 | bool DolovVQsortBatcherSEQ::PostProcessingImpl() { | |
| 35 | 48 | GetOutput() = std::move(res_array_); | |
| 36 | 48 | return true; | |
| 37 | } | ||
| 38 | |||
| 39 | 3328 | int DolovVQsortBatcherSEQ::GetHoarePartition(double *array, int low, int high) { | |
| 40 | 3328 | double pivot = array[low + ((high - low) / 2)]; | |
| 41 | 3328 | int i = low - 1; | |
| 42 | 3328 | int j = high + 1; | |
| 43 | |||
| 44 | while (true) { | ||
| 45 | 8624 | i++; | |
| 46 |
2/2✓ Branch 0 taken 7552 times.
✓ Branch 1 taken 8624 times.
|
16176 | while (array[i] < pivot) { |
| 47 | 7552 | i++; | |
| 48 | } | ||
| 49 | 8624 | j--; | |
| 50 |
2/2✓ Branch 0 taken 8608 times.
✓ Branch 1 taken 8624 times.
|
17232 | while (array[j] > pivot) { |
| 51 | 8608 | j--; | |
| 52 | } | ||
| 53 |
2/2✓ Branch 0 taken 3328 times.
✓ Branch 1 taken 5296 times.
|
8624 | if (i >= j) { |
| 54 | 3328 | return j; | |
| 55 | } | ||
| 56 | std::swap(array[i], array[j]); | ||
| 57 | } | ||
| 58 | } | ||
| 59 | |||
| 60 | 40 | void DolovVQsortBatcherSEQ::ApplyQuicksort(double *array, int low, int high) { | |
| 61 | std::stack<std::pair<int, int>> stack; | ||
| 62 | stack.emplace(low, high); | ||
| 63 | |||
| 64 |
2/2✓ Branch 0 taken 6696 times.
✓ Branch 1 taken 40 times.
|
6736 | while (!stack.empty()) { |
| 65 | std::pair<int, int> range = stack.top(); | ||
| 66 | stack.pop(); | ||
| 67 | |||
| 68 |
2/2✓ Branch 0 taken 3328 times.
✓ Branch 1 taken 3368 times.
|
6696 | if (range.first < range.second) { |
| 69 | 3328 | int p = GetHoarePartition(array, range.first, range.second); | |
| 70 |
2/2✓ Branch 0 taken 2152 times.
✓ Branch 1 taken 1176 times.
|
3328 | if (p - range.first < range.second - p) { |
| 71 |
2/4✓ Branch 1 taken 2152 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2152 times.
✗ Branch 5 not taken.
|
2152 | stack.emplace(p + 1, range.second); |
| 72 | stack.emplace(range.first, p); | ||
| 73 | } else { | ||
| 74 | stack.emplace(range.first, p); | ||
| 75 |
1/2✓ Branch 1 taken 1176 times.
✗ Branch 2 not taken.
|
1176 | stack.emplace(p + 1, range.second); |
| 76 | } | ||
| 77 | } | ||
| 78 | } | ||
| 79 | 40 | } | |
| 80 | |||
| 81 | } // namespace dolov_v_qsort_batcher | ||
| 82 |