自分は実際にC++でソートアルゴリズムの速さを計ったのでそれについて話します。
実際に計った結果は、100万の長さのランダムな配列を揃えさせた場合です。
ms、ミリ秒単位です。
多少誤差があります。
クイックソート
- とりあえずインプレース(配列の2か所を入れ替える作業を使って完結する)ソート内でかなり速い
- 特定のパターン等に弱く、計算量が最大
O(n^2)になってしまう - 再帰呼出がある
実際の結果は、372msです。
ヒープソート
- クイックソートと同じくインプレースソートである
- 再帰呼出がある
- クイックソートと違い、安定して計算量
O(n logn)を出せる - 計算量的にはクイックソートより速いが実際はそれよりちょっと遅い
実際の結果は505msです。
マージソート
- インプレースではなく、揃える配列の長さ分の追加の配列が必要
- 再帰呼出がある
- 揃えた後、揃える前の状態が、同じ要素の相対的な順序が同じになる(安定ソート)
- まあまあ遅い(
O(n^2)よりは速い)
実際の結果は727msです。
基数ソート(LSD)
ここのLSDは、薬物ではなく、Least Significant Digitの略、
最下位桁の意味で、最下位桁から揃えるという意味です。
- マージソートと同じく、揃えた後、揃える前の状態が、同じ要素の相対的な順序が同じになる(安定ソート)
- 圧倒的に速い
- メモリが必要で、バージョンによるが揃える配列の長さの揃える基数倍ぐらい必要
実際の結果は195msです。(速い。)
スムースソート
- ヒープソートの亜種
- 安定ソートではない
- 複雑
- 結構遅いが計算量的には最適計算量が
O(n)なので速いはず
実際の結果は1769msです。(遅い。)
まとめ
| 名前 | 安定? | 結果 | メモリについて |
|---|---|---|---|
| クイックソート | いいえ | 372ms | インプレース |
| ヒープソート | いいえ | 505ms | インプレース |
| マージソート | はい | 727ms | 配列の長さ分 |
| 基数ソート(LSD) | はい | 195ms | 配列の長さ分x揃える基数 |
| スムースソート | いいえ | 1769ms | インプレース |
好評でしたら増やします。最後まで見てくれてありがとうございます。