Templated Quicksort

Original

quicksort.h

#include 

namespace quicksort {

template 
struct traits 
{
    static iterator choose_pivot (iterator first, iterator last) {
        return first + (last - first) / 2 ;
    }

    static iterator partition (iterator first, iterator last, iterator pivot) {
        --last ;
        traits::swap (*pivot, *last) ;
        pivot = last ;

        while (true) {
            while (*first = last) {
                traits::swap (*pivot, *first) ;
                return first ;
            }

            traits::swap (*first, *last) ;
            ++first ;
        }
    }

    static void swap (value_type &lhs, value_type &rhs) {
        std::swap (lhs, rhs) ;
    }
};

template 
void sort (iterator first, iterator last)
{
    if (first >= last) {
        return ;
    }

    auto pivot = traits::choose_pivot (first, last) ;
    auto next_pivot = traits::partition (first, last, pivot) ;
    sort  (first, next_pivot) ;
    sort  (next_pivot + 1, last) ;
}

} // end of namespace quicksort

Driver.cpp

#include "quicksort.h"
#include 
#include 
#include 

template  class Container>
void print_container (const Container  &container)
{
    for (const DataType &d : container) {
        std::cout  class Container>
void run_test (const std::string &name, Container  &&container)
{
    std::cout  (container) ;
    quicksort::sort ::iterator, DataType> (std::begin (container), std::end (container)) ;
    std::cout  (container) ;
}

int main (void)
{
    run_test  ("vec1", std::vector  {5, 4, 3, 1, 2}) ;
    run_test  ("vec2", std::vector  {5, 4, 10, 7, 6, 11, 14, 17, 12, 3, 1, 2}) ;

    return 0 ;
}

Updated

quicksort.h

```
#include
#include

namespace quicksort {
namespace detail {

struct first_pivot_selector
{
template
static Iterator choose_pivot (Iterator first, Iterator last) {
return first ;
}
};

struct middle_pivot_selector
{
template
static Iterator choose_pivot (Iterator first, Iterator las

Let's start with things that can be cleaned up in your traits struct:

Firstly, by convention, all template parameters should be UpperCaseFirstLetter. Secondly, you don't need to pass in a value_type, because you can get this directly from the iterator using std::iterator_traits. Finally, using a struct with all static functions smells a bit: this should simply be an inner namespace. Usually, when it's details that you don't want to expose to people, the chosen name for the namespace would be detail. Let's apply that to the choose_pivot function:

#include 

namespace quicksort
{
namespace detail
{

template 
Iterator choose_pivot(Iterator first, Iterator last)
{
    auto distance = std::distance(first, last) / 2;
    std::advance(first, distance);
    return first;
}

} // end namespace detail

...

It's now using std::distance and std::advance. This will work with any iterator type, but performance will obviously be degraded. If you want to enforce that the iterator is random access, you can always throw in a static_assert:

static_assert(std::is_same::iterator_category,
                            std::random_access_iterator_tag>::value,
               "Iterator must be random access");

The partition function you've got currently could be very easily replaced with std::partition:

template 
Iterator partition(Iterator first, Iterator last, Iterator pivot)
{
    using value_type = typename std::iterator_traits::value_type;
    return std::partition(first, last, [=](const value_type& v) { return v < *pivot; });
}

If you want to make it really customisable, then I'd suggest doing that as template parameters on the sort function. Also, it's always a good idea to provide defaults, because otherwise your users are going to have to specify masses of template parameters, which is annoying. This will require modifying the choose_pivot function above into a struct\class:

namespace detail
{
struct pivot
{
    template 
    Iterator choose_pivot(Iterator first, Iterator last)
    {
        auto distance = std::distance(first, last) / 2;
        std::advance(first, distance);
        return first;
    }
};
} // end namespace detail

Then your sort function would look something like:

template 
void sort(Iterator first, Iterator last)
{
    if (first >= last) {
        return;
    }

    auto pivot = Pivot().choose_pivot(first, last);
    auto next_pivot = detail::partition(first, last, pivot);
    sort(first, next_pivot);
    sort(next_pivot + 1, last);
}

A similar pattern can be used for anything else you want to specify.

Note that we've gotten rid of having to specify template parameters (almost) everywhere. In fact, the same can be done in your run_test function:

...
quicksort::sort(std::begin(container), std::end(container));
...

The compiler is smart enough to deduce parameters, so let it do the hard work.

StackExchange Code Review Q#37474, answer score: 8