Modern, C++ compliant, quick sort

Question

This is a kind of follow up to my previous sort implementation review with specific questions to quick sort, and Modern C++ idioms.

template<typename BidirIt,
         typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type>>
void partition(BidirIt first,
               BidirIt last,
               BidirIt & pivot,
               Comparator cmp = Comparator())
{
    // Last usually points to end, rather than the last element.
    last--;
    // Until both first and last point to the same element (always going to be the pivot).
    while (first != last)
    {
        auto pivot_val = *pivot;
        while (cmp(*first, pivot_val)) ++first;
        while (cmp(pivot_val, *last)) --last;
        if (first == pivot)
        {
            std::iter_swap(first, last);
            pivot = last;
        }
        else
        {
            if (last == pivot)
            {
                std::iter_swap(first, last);
                pivot = first;
            }
        }
    }
}

std::vector<int> vec{ 1, 4, 5, 3, 2 };

template<typename BidirIt,
         typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type>>
void sort_quick(BidirIt first,
                BidirIt last,
                Comparator cmp = Comparator())
{
    typedef std::iterator_traits<BidirIt>::difference_type dt;
    dt size = std::distance(first, last);

    // Arrays of 0 or 1 elements are considered sorted.
    if (size > dt(1))
    {
        auto pivot = first + size / dt(2);
        ::partition(first, last, pivot);
        // Recursive call on each partititon.
        sort_quick(first, pivot);
        sort_quick(std::next(pivot), last);
    }
}

I am looking for any performance optimizations I may have missed in the algorithm itself, as well as Modern C++ constructs I may not be abiding by for this example.

In particular having to pass pivot by reference to partition and having to update the pivot reference if it gets swapped is pretty ugly, If anyone can think of a way around this I would love to know.

Also just realized this doesn't work with duplicates :|

Answer 1

Correctness

Fix build errors

My compiler indicates that your typedef statement is missing typename before std::iterator_traits<BidirIt>::difference_type dt; Additionally, you can replace the typedef with a using statement, which is more modern:

using dt = typename std::iterator_traits<BidirIt>::difference_type;

Adhere to iterator operations

The line:

auto pivot = first + size / dt(2);

Uses the + operator, which bidirectional iterators do not support. Calling your sort on a std::list will fail to compile. You can make your code compliant with bidirectional iterators by changing the above line to:

const auto offset = size / dt(2);
auto pivot = std::next(first, offset);

Squash the bug!

I don't know the cause, but your program appears to loop forever when I give your algorithm the sequence: 1,8,4,6,5,2,0,3. This is almost certainly not desired behavior.

Code Simplicity

Return the new pivot

You can avoid taking the pivot by reference by changing partition() to return the pivot value. The new function signature would be:

template<typename BidirIt,
typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type>>
BidirIt partition(BidirIt first,
                  BidirIt last,
                  BidirIt pivot,
                  Comparator cmp = Comparator())

And then simply return pivot; at the end of the function. But then this function signature looks familiar:

Use the standard library, Luke!

There already exists a partition() function in the standard library. You can replace your entire partition function with it, and simplify sort_quick():

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

The use of auto in the lambda is a C++14 feature, you will have to write out the correct type if you can only use C++11. Also, using std::partition fixes the loop-forever bug on my "bad" input, but still doesn't quite give correct results.

Minor Issues

Unused comparator

sort_quick() accepts a comparator function argument, but the comparator is never used inside the body of the function.

Restrict Iterator types

Currently you rely on convention that your iterator types are bidirectional. You could produce nicer error messages by using static_assert, possibly like this:

using category = typename std::iterator_traits<BidirIt>::iterator_category;
static_assert(std::is_base_of<std::bidirectional_iterator_tag, category>::value, "This algorithm requires bidirectional iterators.");

Answer 2

One optimization that you can do is fall back to the simpler insertion sort for arrays of size < dt(5).