Merge sort (Тема 20/24: Итераторы → Урок 8/10)

RobertDeMilo

Apr 19th, 2024

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 2.35 KB | None | 0 0

raw download clone embed print report

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <random>
using namespace std;
template <typename It>
void PrintRange(It range_begin, It range_end) {
for (auto it = range_begin; it != range_end; ++it) {
cout << *it << " "s;
}
cout << endl;
}
template <typename RandomIt>
void MergeSort(RandomIt range_begin, RandomIt range_end) {
// 1. Если диапазон содержит меньше 2 элементов, выходим из функции
int range_length = range_end - range_begin;
if (range_length < 2) {
return;
}
// 2. Создаем вектор, содержащий все элементы текущего диапазона
vector<typename RandomIt::value_type> elements(range_begin, range_end);
// 3. Разбиваем вектор на две равные части
auto mid = elements.begin() + range_length / 2;
// 4. Вызываем функцию MergeSort от каждой половины вектора
MergeSort(elements.begin(), mid);
MergeSort(mid, elements.end());
// 5. С помощью алгоритма merge сливаем отсортированные половины
// в исходный диапазон
// merge -> http://ru.cppreference.com/w/cpp/algorithm/merge
merge(elements.begin(), mid, mid, elements.end(), range_begin);
}
int main() {
vector<int> test_vector(10);
// iota -> http://ru.cppreference.com/w/cpp/algorithm/iota
// Заполняет диапазон последовательно возрастающими значениями
iota(test_vector.begin(), test_vector.end(), 1);
// shuffle -> https://ru.cppreference.com/w/cpp/algorithm/random_shuffle
// Перемешивает элементы в случайном порядке
random_device rd;
mt19937 g(rd());
shuffle(test_vector.begin(), test_vector.end(), g);
// Выводим вектор до сортировки
PrintRange(test_vector.begin(), test_vector.end());
// Сортируем вектор с помощью сортировки слиянием
MergeSort(test_vector.begin(), test_vector.end());
// Выводим результат
PrintRange(test_vector.begin(), test_vector.end());
}

Add Comment

Please, Sign In to add comment