ALGORITHM VISUAL GUIDE
ソートアルゴリズムを図で理解する：バブル・挿入・クイック・ヒープソート
テストの点数を低い順に並べたい。商品の価格を安い順に表示したい。そんな「順序を整える」処理がソート（整列）です。結果は同じでも、数字を並び替える手順は何種類もあります。ここでは「今どの数字を見ているか」「どこが確定したか」を見ながら、仕組みをつかみましょう。
バブルソートは、隣同士を比べて交換し、1周するたびに大きい数字が右端へ「泡のように」移動する方式です。
1. そもそも「ソート」とは？
以下の数字を、小さい順に並べることを考えます。小さい順を昇順、大きい順を降順と呼びます。
重要なのは、最後の結果が同じでも途中の状態はアルゴリズムによって違うことです。この違いが、処理速度や必要なメモリに影響します。
2. バブルソート：隣同士を比べ、最大値を右端へ送る
左から右へ順番に隣り合う2つを比較し、左の方が大きければ交換します。1周目には最大値が一番右に確定し、2周目には2番目に大きい値がその左へ確定します。
交換するのは「隣同士」だけ
9と6を比べると9の方が大きいので入れ替えます。次に9と1、さらに9と2を入れ替えると、9が右端に到達します。1周で右端1個が確定しますが、途中には複数回の比較・交換があります。
3. 挿入ソート：トランプの手札を並べるイメージ
手札を左から順に整える場面を想像してください。新しいカードを1枚受け取り、すでに整列済みのカードの中へ正しい位置に差し込む方法です。
すでにほぼ整列しているデータでは、移動回数が少なく高速です。一方、逆順のように位置を大きく変えなければならない場合は時間がかかります。
4. クイックソート：基準値（ピボット）で左右に分ける
クイックソートは、ピボットと呼ぶ基準値を選び、小さい値を左、大きい値を右へ振り分けます。その後、左右のグループを同じ方法で細かく分けていきます。
1, 2
3
5, 9, 6
平均的には高速で、一般的な整列処理によく登場する考え方です。しかし、ピボットの選び方や入力の並びが悪いと、分割が偏り、最悪計算量が O(n²) になります。
5. ヒープソート：木構造を使って最大値を取り出す
ヒープソートでは、まず最大ヒープを作ります。最大ヒープとは「親の値が子の値以上」という関係を持つ二分木です。根（いちばん上）に最大値が来るため、これを配列の末尾へ移し、残りをまたヒープに整えます。
最大ヒープのイメージ。親の値 ≧ 子の値。これはソート開始時の元配列そのものを表す図ではなく、ヒープに作り直した後の一例です。
末尾へ確定した最大値を除き、ヒープを再構成する操作を繰り返します。最悪時も O(n log n) で動作する一方、一般に安定ソートではありません。
6. 4方式を比較してみよう
隣り合う値を比較して交換。右端から順に確定。
例：9が比較・交換を繰り返して右端へ移動
整列済みの部分へ次の値を差し込む。
例：3,5,9 に 6 を入れて 3,5,6,9
ピボットを決めて左右に分け、分割を繰り返す。
例：3 を基準に [1,2] と [5,9,6]
最大ヒープから最大値を取り出して末尾へ確定。
例：木の根にある最大値 9 を末尾へ置く
| 方式 | 平均時間 | 最悪時間 | 安定性* |
|---|---|---|---|
| バブル | O(n²) | O(n²) | 安定 |
| 挿入 | O(n²) | O(n²) | 安定 |
| クイック | O(n log n) | O(n²) | 通常は不安定 |
| ヒープ | O(n log n) | O(n log n) | 通常は不安定 |
O（オーダー）記法は、データ件数 n が増えたとき処理量がどの程度増えるかの目安です。O(n²) は件数が増えると比較回数が急増しやすく、O(n log n) は大規模データで有利なことが多いです。表は典型的な実装を前提としています。
*安定ソートとは、同じキーを持つ要素の元の順序を保持する方式です。例えば点数が同じ生徒を元の出席番号順のまま残したい場合に重要です。
7. 1ステップずつ動かして違いを体験する
次のラボでは、同じ数字列を4方式で並べ替えます。ボタンを押すごとに比較・交換・確定の様子が変わります。特にバブルソートでは、1周目の終わりに最大値が右端へ動いたことを確認してください。
数字が動く！4方式のソート実験室
「次へ」を押して、数字をどう比較・交換しているかを観察してください。紫＝比較中、緑＝確定済み、橙＝ピボットです。
観察のポイント：各周回が終わるたびに、緑の確定領域が右端から左へ広がります。9 → 6 の順に確定していく様子を追いましょう。
このラボは学習用の具体的な実装です。比較回数と交換回数は、この表示アルゴリズムで実行された操作を数えます。クイックソートのピボット選択や最適化、実行時間は実装により異なります。緑色の表示は学習用の進捗表現です。
8. まとめ
バブル＝隣同士を比較して右端へ確定。挿入＝整列済みの中に差し込む。クイック＝ピボットで分割。ヒープ＝木の根から最大値を取り出す。
ソートを理解するときは名前の暗記よりも、「どこを比較するか」「何が確定するか」「どの程度の計算が必要か」に注目すると整理しやすくなります。