Quick Sort Implementation with iterators

Question

Most quicksort examples online use C-style arrays and indexes. I have written below quicksort implementation with STL style iterators. It looks fine to me, but I feel like I may be making more than necessary copies of iterators. I am open for any suggestions/improvements:

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <iterator>
template <typename Iter>
inline Iter partition(const Iter& beg, const Iter& end) {
 using std::swap;
 assert(beg != end);
 auto piv = end;
 --piv; // Pivot is the last element
 auto index_small = beg;
 for (auto index_large = beg; index_large != piv; ++index_large) {
 if (*index_large <= *piv) {
 swap(*index_large, *index_small);
 ++index_small;
 }
 }
 swap(*index_small, *piv);
 return index_small;
}
template <typename Iter>
void quick_sort(const Iter& beg, const Iter& end) {
 if (end - beg > 1) {
 const auto& piv = partition(beg, end);
 quick_sort(beg, piv);
 quick_sort(piv, end);
 }
}
// Test
int main() {
 std::vector<int> vec{ 19, 54, 53, 9, 3, 96, 40, 36, 96, 43, 45,
 78, 57, 6, 12, 100, 36, 15, 27, 45, 80, 39,
 10, 71, 100, 15, 41, 43, 20, 32, 61, 2, 55,
 33, 85, 32, 11, 50, 25, 17, 75, 74, 39, 49,
 50, 17, 18, 55, 63, 81, };
 quick_sort(vec.begin(), vec.end());
 std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
 std::cout << '\n';
}

Answer 1

You have done a great job. Here’s my suggestions:

• Sort the include directives in alphabetical order.

• Instead of using the generic name Iter, it may be a good idea to express the random access requirement: something like RandomIt.

• Iterators should be passed by value, not const reference. Don’t be afraid to copy iterators — they are intended to be lightweight objects that are frequently copied, and passing them by const reference will incur overhead over passing them by value because of the additional indirection.

• It is more logical to use auto piv = std::prev(end);, because int y = x - 1; is more logical then int y = x; --y;, right? (Of course you can use end - 1, but that may be less efficient if the subtraction operator of the iterator isn’t inlined.)

• You can use std::iter_swap instead of manually ADL’ing swap.

• Instead of enforcing <=, consider taking a custom comparator as the standard algorithms do. (Also note that the standard library facilities always use < as the comparator by default. <= is not required unless you provide a custom comparator.)

Also, always choosing last element as the pivot can make the code vulnerable to reversely sorted sequences. You can consider taking a random number generator to randomize the choice if this becomes a problem.

• Deduplicator: Perhaps add that the comparison operator used by the standard library for user-defined types is always <, unless a custom comparator is preferred.

Answer 2

I usually try to stay away from these aspects of C++, so maybe take what I say with a grain of salt.

---

From what I can see, your implementation heavily relies on begin and end being random access iterators. If I'm not mistaken, your implementation should also work (see notes on complexity below) for bidirectional iterators as present e.g. in std::list. A minor change should allow the implementation to work with these iterators as well:

• end - beg > 1 would have to become std::distance(beg, end) > 1. std::distance has linear complexity for birectional iterators and constant complexity for random access iterators. (See std::distance).

and you should be good to go. This is the simplest change that I could think of, but I'm pretty sure that there are more efficient solutions for this check.

Note on complexity: As @L.F. pointed out in a comment, quicksort is not a suitable algorithm for bidirectional iterators with regards to complexity, though. Nevertheless, not all hope is lost since at least std::list has its own method std::list::sort which according to the documentation allows you to perform sorting within the \$\mathcal{O}(n\log{}n)\$ complexity class for compares.

You could also use the following iterator functions to express some of the parts of your code in a different way:

• auto piv = end; --piv; could become auto piv = std::prev(end); (See std::prev)
• ++index_small; could become std::advance(index_small, 1); (See std::advance)

These are not strictly necessary though, since bidirectional iterators also support operator++ and operator--.

You can check an example with std::list on cpp.sh.

• Aykhan Hagverdili: I understand the suggestion about using std::distance, but bidirectional iterators support operator++ and operator--, right? What is the point of using std::prev and std::advance?
• Aykhan Hagverdili: using std::distance to check if the range has more than 1 element seems inefficient for bidirectional iterators. Perhaps an "increase check if end, increase check if end" approach would be better for bidirectional iterators, but I imagine that'd affect efficiency detrimentally for random-access iterators.
• Aykhan Hagverdili: The main reason why I assumed begin and end were random access iterators is that std::sort assumes the same.
• AlexV: I wasn't able to find the reason why the standard dictates to only accept random access iterators in std::sort when looking at the draft. My best guess would be that it allows to use more sorting algorithms in the actual implementation, e.g. Wikipedia seems to hint towards a hybrid algorithm in the GCC.implementation.
• L. F.: I am afraid I have to disagree. Quick sort isn’t suitable for non random access iterators. The time complexity will go beyond quadratic.