こんにちは、鈴木です。
TECHSCORE Advent Calendar 2014 の 6 日目の投稿です。
寒くなってきたのでソーティングアルゴリズムをいくつか実装して、速度を比較しました。
測定用のプログラムは以下の場所で公開しています。
測定結果
まずは測定結果です。
ランダムな整数（int 型）の配列をソートする C++ のプログラムを書いて比較しました。
背景が黄色のセルはその条件（データ数）で最も速かったもの、背景がピンクのセルは 2 番目に速かったものです（時間がかかりすぎて測定を打ち切ったものはグレーです）。
データ数は 2 のべき乗にしたので厳密に速度が逆転するデータ数は分かりませんが、
- データ数が 50 以下なら挿入ソート (Insertion Sort)
- データ数が 5 万以下ならマージソート (Merge Sort)
- データ数がそれより多いならクイックソート (Quick Sort)
といったところでしょうか。
追加のメモリ割り当てが必要なマージソートは使いたくない！ という場合は、
- データ数が 100 以下なら挿入ソート (Insertion Sort)
- データ数が 1000 以下ならコームソート (Comb Sort)
- データ数がそれより多いならクイックソート
が目安になると思います。
高速なソートはデータ数が少ないと遅い
アルゴリズムの本を開くと大抵「クイックソートなどの高速なソートはオーバーヘッドが大きいので、データ数が少ないと O(N^2) のアルゴリズムより遅い」と書かれています。
実際に比較してみると確かにその通りで、特にマージソートは遅いですね。これはマージソートは他のアルゴリズムと違って追加のメモリ割り当て/解放が必要なのでオーバーヘッドがより大きいということでしょう。
クイックソートが高速なのはデータ数が非常に大きくなってから
「データ数が大きくなるとクイックソートが最速」と言われますが、具体的にデータ数がどれくらいになるとクイックソートが高速といえるのかご存知でしたか？
上記の結果を見るとデータ数が 32768 のときにマージソートとほぼ互角。「とりあえずクイックソートを使っておけ」で正解の場合も多いですが、肌感覚として理解していると何かの役に立つかもしれません。
コームソートが意外とがんばる
ところでコームソート (Comb Sort) ってご存知でしょうか？ ものすごく簡単に説明すると「データを一定間隔でざっくりバブルソートする、その間隔を徐々に小さくしていく」というアルゴリズムです。
教科書の中でしか生きられないんじゃないかと思うほどに遅いバブルソートを改良したアルゴリズムがコームソートなのですが、これが意外と速いとは驚きですね。
まとめ
今回はベーシックなソーティングアルゴリズムの速度を比較しました。ソーティングはアルゴリズムの中でも昔からある分野で、通常は言語やライブラリが提供してくれるので自分で実装することは少ないですが、改めて実装して比較してみると面白いですね。
ソーティングアルゴリズムは数多くあるので、興味を持った方は調べてみてください。実践的なアルゴリズムでは introsort や tim sort などがあります。比較をしない bin sort, bucket sort, distribution counting sort, inverse mapping sort なども面白いのでぜひ調べてみてください。
ソーティングアルゴリズムに興味を持った方が一人でも増えたら嬉しいです。
