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?

• Ben Steffan: Why the noexcept? I don't think it gains you anything here. I recommend you this article on noexcept.
• lisovskey: @BenSteffan I heard it removes compiler generated code for handling exceptions and increases performance a bit, isn't it?
• Ben Steffan: It might, or it might not. As I said, please read the article I linked you in my previous comment.
• aschepler: On noexcept: what if the copy constructor or assignment operator of content_type throws? Your program will terminate. It would be much more polite to allow that to propagate so the callers can decide what to do about it.
• lisovskey: @aschepler clear, understood

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.

• Mathieu Guindon: Comments are not for extended discussion; this conversation has been moved to chat.

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);
}

• lisovskey: Have you tested the code you proposed? static_assert doesn't work for some reason (even with std::), binary < should be !=. As I said I prefer the lack of return or break if it possible. And as for noexcept, I don't understand what is going on there, are you swapping first with first?
• lisovskey: I figured out what had been wrong with assert
• Deduplicator: My modified noexcept-construct checks whether the basic operations used are noexcept. But noexcept is an unevaluated context.

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, " "));
}

• lisovskey: Sorry, what left and right construction do you mean? Thanks for the default predicate, it so handy
• Incomputable: @lisovskey, the code uses constructor that will default construct size copies of element type.
• lisovskey: I use only vector constructor, it should always work I suppose
• Incomputable: @lisovskey, when constructing left and right you use 3rd constructor mentioned on this page. I'll write an example tomorrow. Please ping me if I forget. Understanding this is important.
• lisovskey: Okay, so what that constructor can spoil? Can you propose a way better?