Forward-Star を構成する際のソート - その３。

いろいろ工夫は行っているのだが、どうも Quick-Sort を以上の性能を出せない。

Graph  : USA-road-d.USA.gr
#nodes : 23,947,347
#arcs  : 58,333,344
length : [1, 368855]

１．Quick-Sort
DIMACS data　6.707 [sec]
ソート済み　 4.319 [sec]

２．Bucket-Sort（区切りによるソート）
22.128 [sec]

３．Bucket-Sort（区切りによるソート）with スタック
24.781 [sec]

Bucket-Sort は、とても効率的で、各データを１回ずつしか移動しない。
参照も含めても数回ずつしかアクセスしない。
区切りによりそのデータがあるべき場所が分かるので、一気に代入する事が出来るためである。

データをあるべき場所へ移動させると、そこにあるデータに対して同じような操作をする。
そうして初めに移動させた場所までかえってくると、次の正しい場所にないデータを探すことになる。
それを１周とすると USA でも、67 周しかない。