Quick Sort

quickSort.hpp

/* Quick Sort [License: CC-BY-SA]
 *  - Copyright(C) 2011 Kazh. All Rights Reserved.
 */

#ifndef __INC_QUICKSORTH
#define __INC_QUICKSORTH

#include <iterator>
#include <algorithm>

/** Sorts an array by Quick Sort Algorithm
 * @tparam        iter   Random Access Iterator to access the array to sort
 * @param[in,out] begin  Pointer to head of the array to sort
 * @param[in,out] end    Pointer to tail of the array to sort
 */
template <
  typename iter
  >
void quickSort (
  iter begin,
  iter end
  )
{
  iter middle;
  iter p;

  if ( std::distance ( begin, end ) <= 1 )
  {
    return ;
  }

  middle = begin;
  for ( p = begin + 1; p < end; ++p )
  {
    if ( *p < *begin )
    {
      std::iter_swap ( p, ++middle );
    }
  }
  std::iter_swap ( begin, middle );

  quickSort ( begin, middle );
  return quickSort ( middle + 1, end );
}

#endif /* __INC_QUICKSORTH */