# Quick Sort on C++ vector

I've seen other implementations around, but they seem pretty complicated. This seems to work for me, but is there anything I'm missing? Also, any tips on how I can improve the quality of the code is appreciated.

#include <iostream>
#include <vector>

template<typename Iter>
void quickSort(std::vector<typename Iter::value_type>& vec, Iter left,
Iter right) {

auto size = std::distance(left, right);
if (size <= 1) {
return;
}
auto pivot = std::next(right, -1);
if (size == 2 && *pivot < *left) {
std::iter_swap(left, pivot);
}
auto wall = left;
auto curr = left;

while (curr != right) {
if (*curr < *pivot) {
std::iter_swap(wall, curr);
wall++;
}
curr++;
}

std::iter_swap(pivot, wall);
quickSort(vec, left, wall);
quickSort(vec, wall + 1, right);

}

int main() {
std::vector<int> myVec = { 6, 5, 2, 3, 2, 4, 34, 2434, 251, 4, 12, 4, 5,
634, 523, 5, 4, 353, 3, 5, 345, 7, 86786, 8, 7, 9, 1 };
quickSort(myVec, myVec.begin(), myVec.end());
return 0;
}

• I seem to remember having seen quicksort before, even Lomuto partitioning, and a tag for things done time and again: reinventing-the-wheel. – greybeard Mar 8 '18 at 7:45

• You don't need to pass the vector itself. left and right iterators provide all the necessary information.

That said, you pass a correct right: too often people pass it as .end() - 1 which indeed leads to unnecessary complications.

• Partitioning is an important algorithm on its own right and deserves to be factored out.

• The lines

if (size == 2 && *pivot < *left) {
std::iter_swap(left, pivot);
}


serve no purpose. The code works fine without them.

• The trickiest part is achieving best performance.

• The poor choice of pivot may result in quadratic time complexity. In a professional implementation choosing pivot is the most complex part.

• In general, C++ is very good in eliminating tail recursion, but in this particular case it may use some help. Specifically, you'd want to recurse into smaller partition, and iterate over the larger one.

• Another optimization is a timely switch to insertion sort. Instead of descending all the way to size <= 1 it is beneficial to stop recursion earlier (say, when size <= 16). Once the recursions are completed, the range is almost sorted, and insertion sort runs in linear time.

• Thank you for your answer. Really insightful. I had to also change the first if statement to if (size <= 2)return; For some reason, instead of throwing a run-time error, Visual Studio just crashes... – Jarrett Johnson Mar 8 '18 at 6:09
• The special case for size == 2 serves no purpose while missing the terminal return. – greybeard Mar 8 '18 at 7:50

• code shall be documented. You may find (and justify) (succinct) presentations like yours in print media, where it doesn't easily get separated from the explanations due - with program code, there's copy&paste. A programming language may or may not have a standard for documenting purpose and limits of a construct. I'm not aware of such for "the C-family", I use&recommend doxygen.
• must read: templaterex' How to Implement Classic Sorting Algorithms in Modern C++
• vnp implied you'd not want to recurse into the larger partition - that is a matter of correctness even more than experiencing (intolerable) run time quadratic in the number of items to sort:
in the worst case, you'd nest one call per item, possibly hitting a limit on stack space or nesting depth.
• this worst case occurs if picking pivot as shown for (almost) pre-ordered items - a deplorably, even disagreeably frequent use case.
• reduce the visual impact of special casing:

if (size < QUICK_LIMIT) {
if (size <= 1) {
return;
auto other = std::next(left);
if (2 == size && *other < *left) {
std::iter_swap(left, other);
return;
}
// handle 2 < size < QUICK_LIMIT
}