doubleのRadixSort

バケットソートの欠点を補える基数ソート(RadixSort)

バケットソートは計算量O(N)の素晴らしい必殺技ですが、
如何せんバケツのサイズに限度があり、用途が限定されます。
この問題を、痛みを伴いながら一部解決できる方法として、基数ソートが上げられます。

ちなみに、バケットソートや基数ソート等ソートアルゴリズムの基本は、この本がおススメです。

データ構造とアルゴリズム (新・情報 通信システム工学)

doubleの配列を基数ソートで

この基数ソートをdoubleの配列に適用してみようという今回の試み。
doubleの配列を1バイト毎にバケットソートすれば、なんと配列のソートが完成するというものです。
素直に実装してみるとこのような感じになりました。
ターゲットはIEEEのreal*8、ソースはlittle-endian依存です。

union DataDouble {
  double d;
  u_char c[8];
};

typedef std::list<DataDouble> List ;
typedef List::const_iterator ListIter ;

typedef std::array<List, 256> Array ;
typedef Array::iterator ArrayIter ;

void RadixSort( std::vector<double>& array )
{
  size_t size = array.size() ;
  
  // byte毎の操作用に共用体に移し替え
  std::vector<DataDouble> target ;
  target.resize(size) ;
  for ( size_t i = 0 ; i < size ; ++i ) {
    target[i].d = array[i] ;
  }

  //1byte毎にバケットソート
  Array box;
  size_t digit = 8 ;
  size_t minusStartIndex = 0;
  for ( size_t i = 0 ; i < digit ; ++i ) {
    for ( auto j : target ) {
      box[j.c[i]].push_back(j) ;
    }
    
    size_t count = 0 ;
    for ( ArrayIter aIt = box.begin(), aEnd = box.end() ; aIt != aEnd ; ++aIt ) {
      for ( ListIter lIt = aIt->begin(), lEnd = aIt->end() ; lIt != lEnd ; ++lIt ) {
        if ( ( i == digit - 1 ) && ( lIt->c[i] & 0x80 ) && minusStartIndex == 0 ) {
          minusStartIndex = count;
        }
        target[count++] = *lIt ;
      }
      aIt->clear() ;
    }
  }

  //負値を考慮  
  std::reverse( target.begin(), target.begin() + minusStartIndex );
  std::reverse( target.begin(), target.end() );
  
  for ( size_t i = 0 ; i < size ; ++i ) {
    array[i] = target[i].d ;
  }
}

さて、ここから高速化にトライ？