ソートあれこれ - その２。

ひとまず、分かっていることを並べてみる。

１．比較回数・代入回数に関して
比較回数・代入回数が多いと実行時間に影響が出てくるが、
少ないから良いというわけでもない。

これは正直驚いた。
比較回数・代入回数は、ソートアルゴリズムに関して最も大きなウェイトを占めていると感じていたが、どうやらそうでもないようである。理由に関しては前回までの記事を確認して頂きたい。


２．データアクセスの局所性
Quick-Sort と Bucket-Sort での実行結果のみでは何とも言えないが、
確かに Quick-Sort の方が局所性という意味では良いように思える。


いくつか実際に実装してみてから、比べていこう。