Comb Sort

combSort.hpp

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

#ifndef __INC_COMBSORTH
#define __INC_COMBSORTH

#include <iterator>
#include <algorithm>
#include "insertionSort.hpp"

/** Sorts the array by Comb 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 combSort (
  iter begin,
  iter end
  )
{
  size_t gap = std::distance ( begin, end ) * 10 / 13;

  /** Comb Pre-Sort */
  while ( gap > 1 )
  {
    for ( iter p = begin, q = begin + gap;
          q < end;
          q = ++p + gap )
    {
      if ( *p > *q )
      {
        std::iter_swap ( p, q );
      }
    }

    gap = gap * 10 / 13;
  }

  /** Insertion Sort */
  insertionSort ( begin, end );

  return ;
}

#endif /* __INC_COMBSORTH */