ソートアルゴリズムの可視化
バブル・挿入・マージ・クイックなど 7 種類のソートが配列を並べ替える様子を棒グラフのアニメーションで見せます。同じデータで並べて比べたり、1 手ずつ確かめたりできます。
- 未確定
- 比較中
- 交換・書き込み中
- 位置が確定
バブルソート
0 / 756 手
- 比較
- 0
- 書き込み
- 0
挿入ソート
0 / 600 手
- 比較
- 0
- 書き込み
- 0
マージソート
0 / 266 手
- 比較
- 0
- 書き込み
- 0
クイックソート
0 / 202 手
- 比較
- 0
- 書き込み
- 0
使い方
- 見たいアルゴリズムを選んで「再生」を押します。複数選ぶと、同じデータを並べ替える様子を並べて比べられます。
- 「1 手」は 1 回の比較、または 1 回の交換・書き込みです。どのアルゴリズムも同じ速さで 1 手ずつ進むので、早く終わるほど手数が少ないことになります。
- 手数のスライダーで好きな場面に移動できます。「1 手戻る」「1 手進む」で 1 手ずつ確かめられます。
- 要素数と並び方（ランダム・ほぼ整列済み・逆順・重複が多い）を変えると、データの形によって得意・不得意が変わる様子が分かります。
- キーボードでは Space で再生 / 一時停止、← → で 1 手戻る / 進む、Home で最初へ、N で新しいデータにします。
- 書き込み回数は配列に値を書いた回数で、交換は 2 回と数えます。
アルゴリズムの特徴
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) | ○ | 整列済みの部分に 1 つずつ差し込む。ほぼ整列済みのデータに強い |
| シェルソート | O(n log n) | O(n^1.25) 程度 | O(n^1.5) | O(1) | × | 離れた要素どうしで挿入ソートをしてから、間隔を縮めていく |
| マージソート | O(n log n) | O(n log n) | O(n log n) | O(n) | ○ | 半分に分けてそれぞれ並べ、整列済みの 2 列を合わせる |
| クイックソート | O(n log n) | O(n log n) | O(n²) | O(log n) | × | 軸より小さい値と大きい値に分けることを繰り返す。重複が多いと遅くなる |
| ヒープソート | O(n log n) | O(n log n) | O(n log n) | O(1) | × | 最大ヒープを作り、根（最大値）を末尾へ移すことを繰り返す |
「安定」は、同じ値の要素どうしの順番が並べ替えの前後で変わらないことです。