計算量の表を丸暗記しても、速さの違いは体感できません。
棒が動くところを見ると、「なぜ遅いのか」が形で分かります。
6つのソートを、同じ条件で見比べられるようにしました。
擬似コードの実行中の行が光り、2つのアルゴリズムを同時に走らせて比べられます。
擬似コード
結果の記録
| 手順 | 並び | n | 比較 | 交換 |
|---|
見方
- 棒の高さが値です。低い順に並べ替えます
- 白い棒が「いま見ている位置」、水色が「比べている相手」、黄色がクイックソートの基準値（ピボット）です
- 緑になった棒は、位置が確定したものです
- 右側の擬似コードは、いま実行している行が光ります。棒の動きとコードの行が対応して見えます
- 「1手」ボタンを押すと、1ステップずつ進みます。コードを目で追いながら確かめたいときに使ってください
- 「くらべる」を押すと、同じ配列に対して2つのアルゴリズムを同時に走らせ、上下に並べて比較できます
- 右下の結果の記録に、比較回数と交換回数が残っていきます
- 「音」を押すと、棒の高さが音の高さになります
見比べるとおもしろい組み合わせ
- 挿入ソート × ほぼ整列済み：ほとんど動かずに終わります。実務で小さい配列に使われる理由が見えます
- 挿入ソート × 逆順：同じアルゴリズムが、最悪のケースでどれだけ粘るかが分かります
- クイックソート vs 挿入ソート（くらべる）：同じ56個で、比較回数が3倍近く違います
- 選択ソート × どれでも：比較回数はいつも同じ。交換回数だけが極端に少ないのが特徴です
- クイックソート × 同じ値が多い：基準値の選び方によって、分割が偏る様子が見えます
- マージソート × ばらばら：合流の場面で、値がまとまって書き戻されるのが見えます
「安定」とは、同じ値どうしの順番が元のまま保たれることです。
名前順に並べたあと点数順に並べ替えても、同点の人の名前順が崩れない、という性質です。
「安定」なソートとは
並べ替え前：名前順（ア→イ→ウ→エ）点数の高い順に並べ替えた後
安定なソート（例：マージソート）
アベ80点
イトウ70点
ウエダ80点
エンドウ70点
○ 同点どうしは名前順のまま
安定でないソート（例：クイックソート）
アベ80点
イトウ70点
ウエダ80点
エンドウ70点
✕ 同点どうしの名前順が崩れることがある
※名前と点数は説明用の架空の例です。安定でないソートの並びは、崩れる場合の一例です。
クイックソートは最悪がO(n²)なのに、実務でよく使われます。
理由は、平均が速いうえに配列の隣り合う場所を読み書きするため、実際の機械の上では表の数字以上に速く動くからです。
JavaのArrays.sort()も、プリミティブ型にはクイックソート系（デュアルピボット）、オブジェクトには安定なマージソート系（TimSort）と使い分けています。
表だけ見ていると、この使い分けの理由は出てきません。
