2 March 2013

Quick sort implementation

Yesterday I tried to implement the quick sort algorithm in C++. I think everyone knows the algorithm, and it seems very easy-to-do stuff, but it took me about 1.5 hours to complete and polish it. So I thought it might be useful for some people and decided to share my implementation. I put in very descriptive comments, so I don't think I need to add anything else, the code follows:


// <iterator> header contains the definitions of
// std::advance, std::distance and std::iterator_traits
#include <iterator>

// SelectPivot is used to select the pivot element in
// the sequence which will serve as a partition point.
// Returns an iterator pointing to the pivot element.
template <typename Iter>
Iter SelectPivot(Iter begin, Iter end)
{
       // Current implementation just returns the middle element,
       // but we are free to choose the pivot in any other way.
       std::advance(begin, std::distance(begin, end) / 2);
       return begin;
}

// Implements the quick sort algorithm.
template <typename Iter, typename Cmp>
void QuickSort(Iter begin, Iter end, Cmp less)
{
       // No need to sort an empty or a single-element sequence.
       if (std::distance(begin, end) < 2)
       {
              return;
       }

       // Select the pivot element and store
       // its value in 'val' variable.
       Iter pivot = SelectPivot(begin, end);
       std::iterator_traits<Iter>::value_type val = *pivot;

       // Introduce new iterators to operate on,
       // begin and end will be needed for recursive
       // calls, so we do not modify them.
       Iter left = begin;
       Iter right = end;

       // Like all the similar algorithms in STL, our function accepts
       // a pair of iterators, pointing to the first and one beyond
       // the last elements respectively. That's why we should not
       // consider the value pointed to by 'end'.
       std::advance(right, -1);

       // Move the pivot element to the end of the sequence.
       std::swap(*pivot, *right);

       // The following piece of code partitions the whole into
       // two sub-sequences so that all the elemets less than the
       // pivot appear to the left from pivot and all the greater
       // elements appear to the right. This means that the chosen
       // pivot element will be in its final place.
       Iter pivot_position = left;

       while (left != right)
       {
              if (less(*left, val))
              {
                     std::swap(*left, *pivot_position);
                     std::advance(pivot_position, 1);
              }
              std::advance(left, 1);
       }

       // The pivot_position now points to the first
       // element which is not 'less' than the pivot. So we
       // need to swap the pivot stored in the rightmost
       // element with that stored in pivot_position.
       std::swap(*pivot_position, *right);

       // Calling the function recursively to
       // sort the sub-sequences to the left
       // and right from the pivot. The latter
       // is already in its final position.
       right = pivot_position;
       std::advance(right, 1);

       QuickSort(begin, pivot_position, less);
       QuickSort(right, end, less);
}