| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "kopilov_d_shell_merge/seq/include/ops_seq.hpp" | ||
| 2 | |||
| 3 | #include <algorithm> | ||
| 4 | #include <cstddef> | ||
| 5 | #include <iterator> | ||
| 6 | #include <utility> | ||
| 7 | #include <vector> | ||
| 8 | |||
| 9 | #include "kopilov_d_shell_merge/common/include/common.hpp" | ||
| 10 | |||
| 11 | namespace kopilov_d_shell_merge { | ||
| 12 | |||
| 13 | namespace { | ||
| 14 | |||
| 15 |
2/2✓ Branch 0 taken 64 times.
✓ Branch 1 taken 16 times.
|
80 | void ShellSort(std::vector<int> &vec) { |
| 16 | const std::size_t n = vec.size(); | ||
| 17 |
2/2✓ Branch 0 taken 64 times.
✓ Branch 1 taken 16 times.
|
80 | if (n < 2) { |
| 18 | return; | ||
| 19 | } | ||
| 20 |
2/2✓ Branch 0 taken 104 times.
✓ Branch 1 taken 64 times.
|
168 | for (std::size_t gap = n / 2; gap > 0; gap /= 2) { |
| 21 |
2/2✓ Branch 0 taken 264 times.
✓ Branch 1 taken 104 times.
|
368 | for (std::size_t i = gap; i < n; ++i) { |
| 22 | 264 | const int tmp = vec[i]; | |
| 23 | std::size_t j = i; | ||
| 24 |
4/4✓ Branch 0 taken 320 times.
✓ Branch 1 taken 96 times.
✓ Branch 2 taken 152 times.
✓ Branch 3 taken 168 times.
|
416 | while (j >= gap && vec[j - gap] > tmp) { |
| 25 | 152 | vec[j] = vec[j - gap]; | |
| 26 | j -= gap; | ||
| 27 | } | ||
| 28 | 264 | vec[j] = tmp; | |
| 29 | } | ||
| 30 | } | ||
| 31 | } | ||
| 32 | |||
| 33 | 40 | std::vector<int> SimpleMerge(const std::vector<int> &a, const std::vector<int> &b) { | |
| 34 |
1/2✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
|
40 | std::vector<int> result; |
| 35 |
1/2✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
|
40 | result.reserve(a.size() + b.size()); |
| 36 |
1/2✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
|
40 | std::ranges::merge(a, b, std::back_inserter(result)); |
| 37 | 40 | return result; | |
| 38 | } | ||
| 39 | |||
| 40 | } // namespace | ||
| 41 | |||
| 42 |
1/2✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
|
56 | KopilovDShellMergeSEQ::KopilovDShellMergeSEQ(const InType &in) { |
| 43 | SetTypeOfTask(GetStaticTypeOfTask()); | ||
| 44 |
1/2✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
|
56 | GetInput() = in; |
| 45 | 56 | } | |
| 46 | |||
| 47 | 56 | bool KopilovDShellMergeSEQ::ValidationImpl() { | |
| 48 | 56 | return true; | |
| 49 | } | ||
| 50 | |||
| 51 | 56 | bool KopilovDShellMergeSEQ::PreProcessingImpl() { | |
| 52 | 56 | data_ = GetInput(); | |
| 53 | GetOutput().clear(); | ||
| 54 | 56 | return true; | |
| 55 | } | ||
| 56 | |||
| 57 |
2/2✓ Branch 0 taken 40 times.
✓ Branch 1 taken 16 times.
|
56 | bool KopilovDShellMergeSEQ::RunImpl() { |
| 58 |
2/2✓ Branch 0 taken 40 times.
✓ Branch 1 taken 16 times.
|
56 | if (data_.size() < 2) { |
| 59 | return true; | ||
| 60 | } | ||
| 61 | |||
| 62 | 40 | const auto mid = data_.size() / 2; | |
| 63 |
1/2✓ Branch 2 taken 40 times.
✗ Branch 3 not taken.
|
40 | std::vector<int> left(data_.begin(), data_.begin() + static_cast<std::ptrdiff_t>(mid)); |
| 64 |
1/4✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
|
40 | std::vector<int> right(data_.begin() + static_cast<std::ptrdiff_t>(mid), data_.end()); |
| 65 | |||
| 66 | 40 | ShellSort(left); | |
| 67 | 40 | ShellSort(right); | |
| 68 | |||
| 69 |
2/6✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 40 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
|
80 | data_ = SimpleMerge(left, right); |
| 70 | return true; | ||
| 71 | } | ||
| 72 | |||
| 73 | 56 | bool KopilovDShellMergeSEQ::PostProcessingImpl() { | |
| 74 | 56 | GetOutput() = std::move(data_); | |
| 75 | 56 | return true; | |
| 76 | } | ||
| 77 | |||
| 78 | } // namespace kopilov_d_shell_merge | ||
| 79 |