Быстрая сортировка на C++

#алгоритм #сортировка #cpp

Приведите пример алгоритма быстрой сортировки на C++.     

Ответы

Ответ 1

Наиболее сложная часть быстрой сортировки - это выбор опорного (pivot) элемента.
В самой простой реализации берется элемент в середине последовательности. Если элементы
равномерно перемешаны, но он ничем не хуже (и ничем не лучше) остальных элементов:

template>
void quick_sort(ForwardIter first, ForwardIter last, Compare cmp = Compare{}) {
    auto n = std::distance(first, last);
    if (n < 2) return;
    auto pivot = std::next(first, n / 2);

    auto less_than_pivot = [=](const auto& x){ return cmp(x, *pivot); };
    auto middle1 = std::partition(first, last, less_than_pivot);

    auto greater_than_pivot = [=](const auto& x){ return !cmp(*pivot, x); };
    auto middle2 = std::partition(middle1, last, greater_than_pivot);

    // assert(std::all_of(middle1, middle2, [=](const auto& x){ return x == *pivot; }));
    quick_sort(first, middle1, cmp);
    quick_sort(middle2, last, cmp);
}


Можно искать медиану при помощи стандартной функции std::nth_element, которая также
сделает частичную сортировку (partition) относительно этой медианы

template>
void quick_sort(RandomAccessIter first, RandomAccessIter last, Compare cmp = Compare{}) {
    auto middle = std::next(first, std::distance(first, last) / 2);
    if (first == middle ) return;  // distance < 2, nothing to sort
    std::nth_element(first, middle, last, cmp); // O(n) on average.
    quick_sort(first, middle, cmp);
    quick_sort(middle, last, cmp);
}


Но это уже будет какая-то гибридная сортировка, а не quick sort.


Ответ 2

#include 

template 
inline void swap( T & arg1, T & arg2)
{
    T temp = arg1;
    arg1 = arg2;
    arg2 = temp;
};
template 
inline int get_median_index( std::vector & vArray, int lower, int upper)
{
    if ((upper-lower) < 2) return lower;

    int middle = (upper+lower)/2;

    if (vArray[lower] <= vArray[middle])
    {
        if (vArray[middle] <= vArray[upper])
        {   return middle;  }
        else if (vArray[upper] <= vArray[lower])
        {   return lower;   }
        else
        {   return upper;   }
    }
    else
    {
        if (vArray[lower] <= vArray[upper])
        {   return lower;   }
        else if(vArray[upper] <= vArray[middle])
        {   return middle;  }
        else 
        {   return upper;   }
    }
    return lower;
};
template 
inline int partition( std::vector & vArray, int start, int end, int median_index)
{
    int head = start, tail = end-1;
    swap( vArray[median_index], vArray[end]);
    while (true)
    {
        while (vArray[head] < vArray[end]) 
        {   ++head; }
        while (vArray[tail] > vArray[end] && tail > start) 
        {   --tail; }
        if ( head >= tail)
        {   break;  }
        swap( vArray[head++], vArray[tail--]);
    }
    swap( vArray[head], vArray[end]);
    return head;
};
template 
inline void quick_sort_helper( std::vector & vArray, int head, int tail)
{   
    int median_index, diff = tail-head;

    if (diff < 1)
    {   return; }
    if (diff == 1)
    {
        if (vArray[head] > vArray[tail])
        {   swap( vArray[head], vArray[tail]);  }
    }

    median_index = get_median_index(vArray, head, tail);
    median_index = partition( vArray, head, tail, median_index);

    quick_sort_helper( vArray, head, median_index-1);
    quick_sort_helper( vArray, median_index+1, tail);
};
template 
void quick_sort( std::vector & vArray)
{   
    int head = 0, tail = vArray.size()-1;
    quick_sort_helper( vArray, head, tail); 
};