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.
noexcept
? I don't think it gains you anything here. I recommend you this article on noexcept. \$\endgroup\$ – Ben Steffan Jun 11 '17 at 14:12noexcept
: what if the copy constructor or assignment operator ofcontent_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. \$\endgroup\$ – aschepler Jun 11 '17 at 17:12