block sort 実装中。

Program

block sort。
だれしもあこがれた事のあるソートのような気がする。
しかし、遅いはアルゴリズムはよくわからんわ！で・・・。今まで躊躇していましたよ。実装するのを。

って事で実装する為に・・・備忘録をつけとこ。

  • ソートしたい配列のサイズ(以下 a1) の2乗分のバッファが必要だが、a1 * 2のサイズで十分。例えば、abcは abc bca cab のパターンがある。3*3 == 9である。しかし、char *p = abcabc; で p[0] だとabc p[1] だと　bca　p[2] だと cab p[3] でabc...　だからである。
  • ブロックソートのソートアルゴリズムは普通にソートする関数にぶち込んでも意味がないらしい。


ちなみに私が理解したblock sort のフロー

  • 一つ一つシフトした配列を容易。
  • 一つ一つをシフトした配列を配列のポインタにぶち込む。
  • 配列自体を要素として*1を辞書順にソート。つまり配列へのポインタを用意して、配列の中身を見てそれを元に配列へのポインタをソートするみたいな。
  • そのソ―トされた配列へのポインタの中の一つ一つシフトした配列の中に元と同じ配列を探してそのソートされた配列へのポインタの配列番号を出力
  • ソートされた配列へのポインタ中の一つ一つシフトした配列の中の最後尾の要素を順に出力。

ゴメン、凄く分かりにくいと思う・・・。

詳しくはM.Hiroi氏のHPやDO++のAlgorithm Blocksortの解説を見て欲しい。



高速なblock sort ?

http://www.geocities.co.jp/SiliconValley-Oakland/1680/zsaru/zsarub22.html

http://www.isl.cs.gunma-u.ac.jp/~shingo/labo/algo/two-stage.html#new2

*1:配列の中身をソートするのではない