2008年11月20日木曜日

分布数え上げソート

BWT(またはブロックソーティング)の解説で、
分布数え上げソートを初体験。

バゲットソートと似ているが、要素の重複が OK なアルゴリズム。
ぱっと見では、なんでソートされるのか直感的に理解できなかったけど、
この絵である程度掴めた。

まだまだ知らないアルゴリズムがあるんだなぁ。。。