Gnome Sort

gnomeSort.hpp

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

#ifndef __INC_GNOMESORTH
#define __INC_GNOMESORTH

#include <iterator>
#include <algorithm>

/** Sorts the array by Gnome 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 gnomeSort (
  iter begin,
  iter end
  )
{
  for ( iter p = begin; p != end; ++p )
  {
    for ( iter q = p; q != begin; --q )
    {
      if ( *q < *( q - 1 ) )
      {
        std::iter_swap ( q, q - 1 );
      }
      else
      {
        break ;
      }
    }
  }

  return ;
}

#endif /* __INC_GNOMESORTH */