7
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ I seem to remember having seen quicksort before, even Lomuto partitioning, and a tag for things done time and again: reinventing-the-wheel. \$\endgroup\$ – greybeard Mar 8 '18 at 7:45
4
\$\begingroup\$
  • 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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... \$\endgroup\$ – Jarrett Johnson Mar 8 '18 at 6:09
  • \$\begingroup\$ The special case for size == 2 serves no purpose while missing the terminal return. \$\endgroup\$ – greybeard Mar 8 '18 at 7:50
2
\$\begingroup\$

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
    }
    
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.