ソートアルゴリズム10個の実行時間を測ってみた

本ブログで解説してきた、11個のソートアルゴリズム。

これらについて、具体的な説明や計算量の解説はしてきた。

しかし、実際に並び替える時間はどのくらいかかるんだ、という疑問があると思う。

そこで、今回は実際にソートを行い、実行時間を比較してみた。

なお、紹介したのは11個だが、今回計測するのは10個だ。

まあ…ボゴソートは今回の条件だと終わらない可能性が高いので、除外させていただく。

計算量では見えない定数部分の影響も見れると思うので、よかったら参考にしてみてほしい。

計測の前提条件

まずは、前提条件を決めておこう。

計測するソート

計測するソートアルゴリズムは、以下の10個だ。

• バブルソート
• 選択ソート
• 挿入ソート
• クイックソート
• マージソート
• ヒープソート
• シェルソート
• ビンソート
• 分布数え上げソート
• 基数ソート

なお、これらのソートの説明は以下記事にまとめてある。

分からない場合は、そちらも参照しながら見て欲しい。

基本的なソートアルゴリズム11個まとめ | Shino’s Mind Archive

今回使用した言語

今回は、これまでサンプルを紹介してきたJavaScriptで計測を行った。

具体的なソースも紹介したもの通りにしてある。

このサンプルソースも上のまとめ記事内から飛べる各詳細記事に貼ってあるので、それも参照してほしい。

ソートするデータ

ソートするデータは、0から99999までの重複なし10万個の整数データだ。

これを事前にシャッフルしておき、ソート前と後の時刻を取得して、その差でソート時間を計測する。

なお、1回だとデータの形に左右されてしまう可能性があるため、10回ソートを行い、その平均値で出すこととしよう。

また、データの範囲が必要なビンソート、分布数え上げソートに関しては、データの範囲を0以上100万未満までとしてある。

常にデータちょうどの範囲が分かってるとは限らないので、10倍にしておいた。

これらの条件で、計測を行っていこう。

計測結果

では、実際に計測してみた結果だ。

単位はミリ秒。

やはりというべきか、圧倒的なのはクイックソート。

次に速いヒープソートと比べても、3倍ほどの差がついている。

とはいえ、そのヒープソートもかなり速いことが分かるだろう。

そこから比較しないソート系とシェルソートが並んでいる。

シェルソートも、挿入ソートをちょっと改良しただけなのに、結構速くなっていることがわかる。

その挿入ソートを含む、単純なソートアルゴリズムはやはりどれもちょっと時間がかかっている。

これを見る限りでも、やはりそのまま単純なソートアルゴリズムを使うのは避けた方が良さそうだ。

その他で言うと、マージソートが思ったよりも遅いな、という印象。

このマージソートは、連結リストにすると作業用領域が削減できるというメリットがあるので、考える場合はそちらも考慮する必要があるだろうか。

今回のように配列のソートで、ただ速さだけを見る場合にはあまりパッとしない。

今回使用したソースコード

最後に、一応今回使用したソースコードを提示しておこう。

とはいえ、全部貼るとかなり長くなるので、ソート1個分だけ載せる。

また、各ソートの具体的な内容は別記事に出しているので、そちらを参照してほしい。

let data; // ソートするデータ
let count = 10; // ソート回数
let avg = 0;

for(let i = 0; i < count; i++){
    shuffle(data); // データをランダムに並び替え
    start_time = performance.now(); // ソート開始時刻を記録
    // ソート実行
    end_time = performance.now(); // ソート終了時刻を記録
    avg += end_time - start_time; // ソート時間を記録
}
avg /= count; // 1回あたりの平均算出
console.log(avg); // 出力

こんな感じで計測している。

開始、終了時の時刻を記録しておき、その差で実行時間を計測する方法はよく使うので、覚えておくといいかもしれない。

おわりに

今回は、個人的に見てみたかったという理由で各ソートにかかる実際の時間を計測してみた。

ちょっと予想外な結果になったので、試してみてよかったなという感想だ。

実行時間を見るときに計算量を見るのも大事だが、それに頼り切るのも危ないということも分かった。

また、得意なデータ形式や安定かどうかなど実行時間だけでは見えない特徴もあるので、どれを使うかはそこも加味して考えていこう。