Flash sort

by syoyo

http://www.neubert.net/FSOIntro.html

I think flash sort algorithm( O(N) time complexity ) is one of the fastest sorting algorithm in the world.

Flash sort というソートアルゴリズムが、なかなかよさげです。

紹介文には、『クヌースは「その場での(in-situ, つまり extra なメモリ領域がいらない)ソートアルゴリズムは、平均して O(n log n) 時間を要するだろう」という予測をしたが、しかしこれはもうハズレである。新しいアルゴリズムであるこのフラッシュソートは、 O(n) 時間のその場でのアルゴリズムである』とあるくらいですから、なんとも”スゴ味”が伝わってきます。

ソートのアルゴリズムといえば、
 o クイックソート(+ 挿入ソート)
 o 基数ソート
 o bitonic merge sort( GPU とか向け )
がたぶんよく知られている効率的なソートアルゴリズムだと思いますが、
フラッシュソートはこれらよりもより効率よくソートができるソートアルゴリズムではないかと思います。

実際にちょっと試したところ、ランダム値のソートでは、フラッシュソートがもっとも高速でした(もちろん、本来でしたら、ロバスト性を考えるためにいろいろな種類の数値列に対してソートアルゴリズムを試してみる必要があります)。

オフラインレンダリングでは、ほとんどソートが必要になる処理はありませんが、
リアルタイムですと、アルファポリゴンの並べ替え、衝突判定での sweep-and-prune、動的 kd-tree の構築などで良質かつ高速なソートアルゴリズムを必要とするでしょうから、このフラッシュソートを試してみる価値はあるかと思います。 

Advertisements