Krdytkyu

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;

}

• 
  

  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.

  
  
  
  

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
  
  }