ソートアルゴリズムの可視化

八種類のソートを操作できるアニメーションで学びます。バブル、選択、挿入、マージ、クイック、ヒープソートは、要素を比較して順序を決めます。計数ソートはキーを数え、基数ソートは桁ごとに振り分けます。入力を変え、アニメーションとコードを一ステップずつ確認できます。

どのレッスンも、配列を昇順にする問題を扱います。異なるのは手順です。比較、移動、追加領域を見比べると、安定性、インプレース性、入力順序への適応、最悪の場合の違いが分かります。

ソートのどこを見るか

レッスンを開いて入力を変え、再生またはステップ実行します。次の四点を確認します。

• 順序の決め方：バブルソートは隣同士を比較し、選択ソートは未整列部分全体から最小値を探します。マージソートは二つの整列済み列の先頭を比較します。計数・基数ソートは要素同士の大小比較を使いません。
• 安定性：同値の要素が元の順序を保つかを見ます。安定ソートなら、先にあった 12a は 12b の前に残ります。複数のフィールドでレコードを整列するときに役立つ性質です。
• 追加領域：O(1) で済むか、別の配列が必要かを見ます。マージソートは補助配列を使い、O(n log n) の時間を保証します。ヒープソートは元の配列内にヒープを作ります。
• 最悪の場合：クイックソートは O(n²) に退化する場合があります。マージソートは O(n log n) を保ちます。平均時間が同じでも、最悪時間は異なります。

ソートの計算量比較

バブル、選択、挿入ソートの平均時間は O(n²) です。マージ、クイック、ヒープソートの平均時間は O(n log n) です。計数・基数ソートの費用は、キーの範囲や桁数にも依存します。

* バブルソートの最良 O(n) は、交換のないパスで終了する最適化版です。通常版は全パスを実行します。挿入ソートも整列済み入力で O(n) になりますが、選択ソートは残りの走査を省略しません。

† クイックソートの O(log n) は平均的な再帰スタックの深さです。分割が偏り続けると O(n) になります。

‡ k はキーの範囲、d は最大キーの桁数、b は基数です。固定基数なら O(d·n)、基数も変数ならバケットの処理を含めて O(d·(n + b)) です。

§ ヒープソートの表は時間の上界です。同値の親子で sift-down が停止するため、すべての入力で同じ量の処理が必要なわけではありません。

学習の順序

まずバブルソートで、隣同士の交換と二乗回数の比較を見ます。次の選択ソートは一パスにつき最大一回の交換で書き込みを減らしますが、既存の順序を利用しません。挿入ソートでは、整列済みの接頭部分が広がる過程と、乱れの少ない入力で移動が減る理由を確認します。

続いて、平均 O(n log n) の比較ソートを学びます。マージソートは分割後に整列済み列を結合し、O(n) の補助配列を使います。クイックソートは分割でピボットの位置を確定し、分割の偏りが残りの仕事量を左右します。ヒープソートは最大ヒープから最大値を取り出し、データ構造とソートを結びつけます。

最後は要素同士を比較しない二種類です。計数ソートはキーを添字にして数え、累積和で出力位置を求めます。基数ソートは各桁で安定な振り分けを行い、下位桁の順序を引き継ぎます。安定性が正しさの条件になる例です。

すべてのソートレッスン

下のレッスンを選び、入力の変更やステップ実行でアニメーションとコードを確認できます。