Quick sort in C++

Give an example of a quick sort algorithm in C++.

Author: Nicolas Chabanovsky, 2010-10-20
Source

2 answers

The most difficult part of quick sorting is selecting the pivot element. In the simplest implementation, the element in the middle of the sequence is taken. If the elements are evenly mixed, but it is no worse (and no better) than the rest of the elements:

template<typename ForwardIter, typename Compare = std::less<>>
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);
}

You can search for the median using the standard function std::nth_element, which will also do a partial sort (partition) relative to this median

template<typename RandomAccessIter, typename Compare = std::less<>>
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);
}

But this will already be some kind of hybrid sorting, and not quick sort.

 7
Author: Abyx, 2016-03-04 10:30:16 
#include <vector>

template <typename T>
inline void swap( T & arg1, T & arg2)
{
    T temp = arg1;
    arg1 = arg2;
    arg2 = temp;
};
template <typename T>
inline int get_median_index( std::vector<T> & 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 <typename T>
inline int partition( std::vector<T> & 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 <typename T>
inline void quick_sort_helper( std::vector<T> & 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 <typename T>
void quick_sort( std::vector<T> & vArray)
{   
    int head = 0, tail = vArray.size()-1;
    quick_sort_helper( vArray, head, tail); 
};
 3
Author: Nicolas Chabanovsky, 2010-10-20 19:45:20