C++ソートめぐり

たまにTwitterで「クイックソートも書いたことないのか?」といった類のつぶやきを見かけることがあります.そういえば,メジャーどころなのに書いたことないソーティングアルゴリズムって結構あったりして,一回やっておかないとまずい気がしたので書いてみました.言語はC++です.

ソートアルゴリズム

このページを参考にしました.とてもわかりやすくまとまっていて,サンプルコードもあったので,写経のように進めながら考えることができました.ありがとうございます.
いろいろなソートアルゴリズム
実装したのは,6つのアルゴリズムです.

プログラム

今回書いたコードをGithubにアップしました.
https://github.com/glass5er/Sort-Practices
内容は教科書にあるとおりのアルゴリズムだと思うので,特に目新しいことはしていませんが,バグがあるかもしれません.(テストは少ししかしていないので)

最後に

テストスクリプトで実行時間を計ってみたのですが,バブルソートが遅いのはいいとして,基数ソート,クイックソートがあまり早くなりませんでした.たぶんコレクションあたりの実装がまずい気がするので,追い追いなおしていきます.
実用上は,普通にstd::sort()を使うってことでいいんですけどね.