Quick Sort Implementation C++11

Question

Here is qsort implementation using iterators as it is in std::sort

// iterator check
template <typename It, typename T>
constexpr bool is = std::is_same<std::iterator_traits<It>::iterator_category, T>::value;


// quick sort
template <typename BidIt, typename Pred>
void qsort(BidIt first, BidIt last, Pred compare) noexcept
{
    static_assert(is<BidIt, std::bidirectional_iterator_tag> || is<BidIt, std::random_access_iterator_tag>,
        "bidirectional iterator required");

    auto size = std::distance(first, last);

    if (size > 1) {
        using content_type = std::iterator_traits<BidIt>::value_type;

        content_type pivot = *first;
        std::vector<content_type> left(size), right(size);
        auto left_end = left.begin();
        auto right_end = right.begin();

        for (BidIt i = std::next(first); i != last; ++i) {
            compare(*i, pivot) ? *left_end++ = *i : *right_end++ = *i;
        }

        qsort(left.begin(), left_end, compare);
        qsort(right.begin(), right_end, compare);

        std::copy(left.begin(), left_end, first);
        *std::next(first, std::distance(left.begin(), left_end)) = pivot;
        std::copy(right.begin(), right_end, std::next(first, std::distance(left.begin(), left_end) + 1));
    }
}

Your thoughts?

Answer 1

As Incomputable mentioned, TemplateRex's "How to Implement Classic Sorting Algorithms in Modern C++?" post on SO is a must-read.

---

// iterator check
template <typename It, typename T>
constexpr bool is = std::is_same<std::iterator_traits<It>::iterator_category, T>::value;

Don't pollute the global namespace for other users who might use your code. Either wrap your helper trait types in their own namespace or alias the trait type locally.

Template arguments must be a type. Don't forget typename.

---

        content_type pivot = *first;

Pivot selection is important for ensuring performance that avoids the worst case of \$O(n^2)\$. Selecting the leftmost (as you did) or rightmost for a pivot makes quicksort vulnerable to sequences that are either ordered or reverse-ordered.

---

        std::vector<content_type> left(size), right(size);

If you refer to std::vector's constructor documentation, you will notice neither explicit vector( size_type count ); nor the allocator accepting version are noexcept as either could throw. That violates the commitment you made in your function signature that qsort was noexcept.

You are constructing the container with size default-inserted instances of content_type. What happens if content_type is not DefaultInsertable?

---

        for (BidIt i = std::next(first); i != last; ++i) {
            compare(*i, pivot) ? *left_end++ = *i : *right_end++ = *i;
        }

By only partitioning the elements that match your comparator, your partitioning algorithm is likely to exhibit worse-case performance as more elements are repeated in a sequence.

Know your <algorithm>'s. See std::partition_copy.

---

void qsort(BidIt first, BidIt last, Pred compare) noexcept

After examining your entire implementation of qsort, why not allow forward iterator support?

---

Optimizations:

Use a better pivot selection. If you select the ends, you are vulnerable in the worst case on sorted and reversed sorted inputs. If you select the middle element, you are vulnerable to bell-curved inputs. Better Single-Pivot options would include median-of-3 and ninther. There is also a Dual-Pivot approach to quicksort.

For single-pivot partitions, you should guard against sequences with many repeated elements by using three-way partitioning.

Partition in-place. Your partition algorithm wastes a lot of space as it allocates two temporary buffers that cover the full sub-sequence.

You can optimize pivot selection and partitioning to the iterator type. See Alexander Stepanov's Notes on Programming.

Consider using insertion sort at a certain threshold. Insertion sort performs fewer operations (swaps, comparisons, etc) and takes advantage of architecture caching for smaller arrays.

Reduce more space by taking advantage of tail-call optimization. Call qsort into the smaller side first then use a tail-call to recurse into the larger half.

Answer 2

Advice 1

You can save some indentation space:

if (size > 1) {
    ... // Lots of code.
}

to

if (size < 2) {
    return;
}
... // Lots of code here.

Advice 2

You can do the partitioning in-place; there is no need for asking for more memory. The pseudocode in Wikipedia is rather detailed, uses no auxiliary memory (except for the recursion stack, of course) and is easy to follow.

Answer 3

1. You forgot specifying your includes, so they won't be scrutinized. FWIW, you need <iterator>, <type_traits> and <vector>. My changes trade <vector> for <algorithm>.

2. Check for the base-class instead of an exhaustive list of base and all derived types.

3. Insert typename to mark dependent types as types.

4. Provide defaults for template- and function-arguments where ou can for maximum convenience and versatility.

5. Use early-return to completely handle what you can immediately. Remember that the most important resource is the readers limited concentration.

6. Don't limit yourself to copyable types. An additional benefit from not copying the pivot is smaller stack-frames.

7. Avoid allocating additional space, it's expensive. That also allows you to minimize copying.
   See Fastest algorithm of dividing array into positive and negative numbers for an efficient in-place way to divide a range.

8. Are you sure you want to abort your program if sorting fails for any reason? Or was marking the function noexcept just a bit too much?

9. Getting the size of the range is potentially an O(n) operation. Avoid that.

10. The algorithm degenerates to O(n) if all elements are equal.

#include <iterator>
#include <type_traits>
#include <algorithm>

// quick sort
template <typename BidIt, typename Pred
    = std::less<typename std::iterator_traits<BidIt>::value_type>>
void qsort(BidIt first, BidIt last, Pred compare = {})
noexcept(noexcept(compare(*first, *first), std::iter_swap(first, first)))
{
    static_assert(std::is_base_of<std::bidirectional_iterator_tag,
        typename std::iterator_traits<BidIt>::iterator_category>(),
        "at least bidirectional iterator required");

    if (first == last || first == last - 1)
        return;

    const auto& pivot = *first;
    auto left = first; ++left;
    auto right = last;

    do {
        do --right;
        while (left != right && !compare(*right, pivot));
        while (left != right && compare(*left, pivot))
            ++left;
        if (left != right) {
            std::iter_swap(left, right);
            ++left;
        }
    } while (left != right);

    std::iter_swap(first, left - 1);

    qsort(first, left - 1, compare);
    qsort(left, last, compare);
}

Answer 4

General note: std::sort() implementation varies from libc++ to libstdc++, but in general they are far more complicated. This post might be interesting for you.

Thoughts:

• This will not work on non default constructible types (because of left and right construction).

• It would be nice to default Pred to std::less<> (or typed one for C++11) and make compare be defaulted to default construction

  template <..., typename Pred = std::less<>>
  ... ...(..., Pred compare = {}) 
  {
   ...
  }
  

• The code needs typename before std::iterator_traits<BidIt>::iterator_category, since iterator_category is a dependent type.

• The error wording should say "at least" to be concise.

Full code with demo:

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <functional>

// iterator check
template <typename It, typename T>
constexpr bool is = std::is_same<typename std::iterator_traits<It>::iterator_category, T>::value;


// quick sort
template <typename BidIt, typename Pred = typename std::less<typename std::iterator_traits<BidIt>::value_type>>
void qsort(BidIt first, BidIt last, Pred compare = {}) noexcept
{
    static_assert(is<BidIt, std::bidirectional_iterator_tag> || is<BidIt, std::random_access_iterator_tag>,
        "at least bidirectional iterator required");

    auto size = std::distance(first, last);

    if (size > 1) {
        using content_type = typename std::iterator_traits<BidIt>::value_type;

        content_type pivot = *first;
        std::vector<content_type> left, right;
        left.reserve(size);
        right.reserve(size);
        auto left_end = std::back_inserter(left);
        auto right_end = std::back_inserter(right);

        for (BidIt i = std::next(first); i != last; ++i) {
            compare(*i, pivot) ? *left_end++ = *i : *right_end++ = *i;
        }

        qsort(left.begin(), left.end(), compare);
        qsort(right.begin(), right.end(), compare);

        std::copy(left.begin(), left.end(), first);
        *std::next(first, std::distance(left.begin(), left.end())) = pivot;
        std::copy(right.begin(), right.end(), std::next(first, std::distance(left.begin(), left.end()) + 1));
    }
}

struct integer
{
    integer() = delete; //not default constructible
    integer(int y):
                x(y)
    {}

    int x;
};

bool operator<(const integer& lhs, const integer& rhs)
{
    return lhs.x < rhs.x;
}

std::ostream& operator<<(std::ostream& os, const integer& x)
{
    os << x.x;
    return os;
}

int main() {
    std::vector<integer> v{1, 0, -1, 4, 2};
    qsort(v.begin(), v.end());
    std::copy(v.begin(), v.end(), std::ostream_iterator<integer>(std::cout, " "));
}