SORTING CINEMA / LEARN
ソートアルゴリズムの使い方と計算量比較ガイド
ソートは、データを大小などの基準で並べ替える処理です。同じ並べ替えでも、隣同士を交換する方法、配列を分割する方法、数値の桁を使う方法で動きが変わります。Sorting Cinemaでは21種類を無料で可視化し、音・Step操作・レース・クイズを使って学べます。
プログラミング初学者・授業で実演する方へ。文・実装: Karou
可視化アプリの使い方
- バブルソートを12要素で開く。バー表示では高さが数値、横方向が配列の位置です。
- Stepを押すと1操作ずつ進み、比較・交換・配置の説明を確認できます。Playでは連続再生、Stopでは中断します。
- 「ほぼソート済み」「逆順」「同値多数」などのプリセットを切り替え、入力による動きの違いを観察します。音が不要ならSound OFFを選びます。
- レースタブで2〜4種類を選び、同じ入力で見比べます。クイズタブでは動きからアルゴリズム名を予想します。
音階とバー・円形・カラー・散布図の4つの表示を選べます。最初はバー表示、少ない要素数、低めの速度で始めると動きを追いやすくなります。
代表的なソートの計算量と安定性
時間計算量は、要素数nが増えたときの処理量の増え方を表します。O(n²)なら、nを2倍にしたときの主要な処理量はおおむね4倍、O(n log n)なら増え方はそれより緩やかです。安定性は、同じキーを持つ要素の元の順番を保つ性質です。
| アルゴリズム | 最良 | 平均 | 最悪 | 追加領域 | 安定性 |
|---|---|---|---|---|---|
| バブル（早期終了あり） | O(n) | O(n²) | O(n²) | O(1) | 安定 |
| 選択 | O(n²) | O(n²) | O(n²) | O(1) | 通常は不安定 |
| 挿入 | O(n) | O(n²) | O(n²) | O(1) | 安定 |
| マージ | O(n log n) | O(n log n) | O(n log n) | O(n) | 安定に実装可能 |
| クイック | O(n log n) | O(n log n) | O(n²) | 平均O(log n)、最悪O(n) | 通常は不安定 |
| ヒープ | O(n log n) | O(n log n) | O(n log n) | O(1) | 通常は不安定 |
本アプリのバブルソートは、交換がない周回でも早期終了しないため、整列済み入力でも比較はO(n²)です。クイックソートは末尾をピボットに選ぶため、整列済み・逆順・同値多数の入力で分割が偏る場合があります。表はアニメーションの所要時間を予測するものではありません。
カウントソートは値の範囲をkとしてO(n + k)、基数ソートは桁数d・基数bとしてO(d(n + b))が目安です。数値の範囲や桁数という条件があるため、比較ソートより常に速いとは限りません。本アプリは正の整数を扱い、基数ソートは10進数の下位桁から処理します。
クイックソートとマージソートの違いは？
クイックソートはピボットを基準に小さい側・大きい側へ分け、各部分を再帰的に並べます。マージソートは配列を半分ずつに分け、整列した部分を結合します。平均時間計算量はどちらもO(n log n)ですが、クイックは分割の偏りで最悪O(n²)、マージは追加の配列領域を使ってO(n log n)を保ちます。
クイックソートを観察すると、ピボットが最終位置に入る様子を追えます。マージソートを観察すると、短い整列済み部分が長くなる結合の流れを確認できます。
動きで理解する3つの練習課題
1. 大きな値はどこへ移動する？
バブルソートをStepで進めます。1周で大きな値が右側へ移るのを観察し、次の周回で比較する範囲が短くなる理由を説明してみましょう。
2. ほぼ整列済みなら何が変わる？
挿入ソートの「ほぼソート済み」と「逆順」を比べます。各要素が左へ動く距離に注目してください。本アプリの操作数はすべての条件比較を数えているわけではないため、動きと計算量を分けて考えます。
3. 比較せずに並べ替える方法は？
カウントソートで値ごとの個数を利用する流れと、基数ソートで桁ごとに並び直す流れを観察します。「値の範囲が非常に広いときは？」を考えると、適用条件の違いがわかります。
収録している21種類と実装の範囲
- 比較ソート: バブル、選択、挿入、マージ、クイック、ヒープ、シェル、カクテル、ノーム、コム、Tim
- 非比較ソート: カウント、基数、バケット
- 並列処理向けの構造: 奇偶、ビトニック
- 独特な構造: パンケーキ、ストゥージ
- ジョーク: ボゴ、スリープ、スロー
可視化は学習用の実装です。Timは8要素ずつ挿入ソートし、その後マージする簡略版で、実用ライブラリのTimsortにある自然なrunの検出などは再現していません。スリープソートは値で整列した順序をもとに待ち時間を付けるシミュレーションです。奇偶・ビトニックも、このアプリでは逐次的にアニメーションし、並列マシンの性能を測りません。
ボゴ・ストゥージ・スローは要素数を小さくして試してください。Play・Stepではそれぞれ8・20・16要素まで自動縮小します。ボゴソートには試行回数の上限があり、終了時に必ず整列できるとは限りません。
理論の参考: Princeton Algorithms: Elementary Sorts、Mergesort、Quicksort。
よくある質問
無料で使えますか？登録は必要ですか？
可視化・レース・クイズは無料で、アカウント登録なしでブラウザから使えます。
音が出ないときは？
音声はPlayなどの操作後に開始します。Sound ONになっているか、ブラウザのタブがミュートされていないか、端末の音量を確認してください。音を切っても可視化は使えます。
レースの順位で、最速のソートがわかりますか？
この順位は、入力とアニメーションの待ち時間・描画方法に左右されます。操作数も可視化に使った比較・交換・配置などの回数で、実装間で数え方に違いがあります。実行性能の判断には、条件を揃えたベンチマークと計算量の理解が必要です。
同じ値の順番が保たれるか、見られますか？
同値多数プリセットは試せますが、このアプリでは要素に元のIDを表示しません。同じ数値だけでは安定性を見分けられないため、キーと元の順番の両方を持つデータで別途検証する必要があります。
スマートフォンでも使えますか？
タッチ操作に対応したブラウザで使えます。画面が狭い場合は要素数を減らしてください。この比較表は横にスクロールできます。