Quick Sort on C++ vector

Question

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
– greybeard, Commented Mar 8, 2018 at 7:45

vnp · Accepted Answer · 2018-03-08 05:49:33Z

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
– Jarrett Johnson, Commented Mar 8, 2018 at 6:09
The special case for size == 2 serves no purpose while missing the terminal return. — greybeard
– greybeard, Commented Mar 8, 2018 at 7:50

albert · Accepted Answer · 2018-12-16 13:23:35Z

Additions to vnp's take:

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
}

Stack Exchange Network

Quick Sort on C++ vector

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Quick Sort on C++ vector

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions