Быстрая и Пирамидальная сортировка - C++ - Ответ 16878643

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include "Timer.h"
 
#ifdef _DEBUG
#include "MemoryLeakTracker.h"
#endif
 
 
// сортировка Шелла
template<typename it, typename compare>
void shell(it start, it end, compare comp) {
    for (auto step = (end - start) / 2; step > 0; step /= 2) {
        for (auto i = start + step; i < end; i++) {
            for (auto j = i; j - start >= step && comp(*j, *(j - step)); j -= step)
                std::swap(*j, *(j - step));
        }
    }
}
 
// разбиение массива на две части относительно опорного элемента
// (для самодельной быстрой сортировки)
template<class Iter>
Iter partition(Iter first, Iter last)
{
    Iter pivot = last - 1;
    Iter right = first;
    for (auto unknown = first; unknown != last - 1; ++unknown)
    {
        if (*unknown <= *pivot)
        {
            std::iter_swap(right, unknown);
            ++right;
        }
    }
    std::iter_swap(right, pivot);
    return right;
}
 
// самодельная быстрая сортировка
template<class Iter>
void quick_sort(Iter first, Iter last)
{
    if (std::distance(first, last) > 1)
    {
        auto q = partition(first, last);
        quick_sort(first, q);
        quick_sort(q + 1, last);
    }
}
 
 
int main() {
    std::cout << "Enter array size" << std::endl;
    int size;
 
    srand(time(0));
 
    std::cin >> size;
    std::cout << std::endl;
    std::cout << "Elements in array: " << size << std::endl;
    std::cout << std::endl;
 
    std::vector<int> vec(size);
    std::generate(vec.begin(), vec.end(), std::rand);
 
#ifdef _DEBUG
    for (int el : vec)
    {
        std::cout << el << " ";
    }
#endif
 
    std::vector<int> vec2(size);
    std::vector<int> vec3(size);
    std::copy(vec.begin(), vec.end(), vec2.begin());
    std::copy(vec.begin(), vec.end(), vec3.begin());
 
    {
        Timer time("Shell sort");
        shell(vec.begin(), vec.end(), [](int a, int b) { return a < b; });
    }
 
    {
        Timer time("Built-in quick sort (std::sort)");
        std::sort(vec2.begin(), vec2.end(), [](int a, int b) { return a < b; });
    }
 
    {
        Timer time("Custom quick sort");
        quick_sort(vec3.begin(), vec3.end());
    }
}