snakesort.h

Go to the documentation of this file.

#ifndef SNAKESORT_H 
#define SNAKESORT_H

#include <cmath>
using namespace std;

#include <functionalobjectoperators.h>
#include <typedefs.h>


class snakesort
{
public:

  template< typename T, typename CMP >
  static void d1
  (
    T* vi,
    uintc N,
    uintc width,
    CMP compare,
    uintc parity=0
  );

  template< typename T, typename CMP >
  static void d2
  (
    T* vi,
    uintc N,
    CMP compare
  );

  template< typename T, typename CMP >
  static void d3
  (
    T* vi,
    uintc N,
    CMP compare
  );

};



//---------------------------------------------------------
// Implementation


template< typename T, typename CMP >
void snakesort::d1
(
  T* vi,
  uintc N,
  uintc width,
  CMP compare,
  uintc parity
)
{
  uint k=parity;
  for (uint i=0; i<N; i+=width, ++k)
  {
    if (i+width<=N)
    {
      if (k%2)
        sort(vi+i,vi+i+width,mynot2(compare));
      else
        sort(vi+i,vi+i+width,compare);
    }
    else
    {
      if (k%2)
        sort(vi+i,vi+N,mynot2(compare));
      else
        sort(vi+i,vi+N,compare);
    }
  }
}

template< typename T, typename CMP >
void snakesort::d2
(
  T* vi,
  uintc N,
  CMP compare
)
{
  uint width=(int)sqrt(N);
  sort(vi,vi+N,mycomparexobject<CMP>());
  d1(vi,N,width,mycompareyobject<CMP>());
}

template< typename T, typename CMP >
void snakesort::d3
(
  T* vi,
  uintc N,
  CMP compare
)
{
  uint width=(int)pow(N,2.0/3.0);
  uint width2=(int)pow(N,1.0/3.0);
  sort(vi,vi+N,mycomparexobject<CMP>());
  d1(vi,N,width,mycompareyobject<CMP>());
  uint parity=0;
  mycomparezobject<CMP> compare2;
  for (uint i=0; i<N; i+=width)
  {
    if (i+width<N)
      d1(vi+i,width,width2,compare2,parity);
    else
      d1(vi+i,N-i,width2,compare2,parity);
    ++parity;
  }
}


#endif