整列（ソート）アルゴリズムの比較

まず全体像：8つの整列法を一言で

整列（ソート）は、データを小さい順（昇順）か大きい順（降順）に並べ替える処理です。試験に出るのは、整列法の説明文を読んで名前を当てる問題がほとんどです。下の表の「一言でいうと」を言えるようにすれば、名前当ての問題は解けます。

ヒープソートは前のレッスンで学んだヒープを使います。ヒープは「親が子より必ず大きい（小さい）」木なので、根を取ればいつでも最大値（最小値）が手に入ります。

クイックソート：最頻出。「基準値で2つに分ける」

クイックソートは、ピボット（基準値）を1つ選び、それより小さい値のグループと大きい値のグループに分けます。分けた各グループの中でもまたピボットを選び、同じ分割を繰り返します。このように、同じ手順を小さい範囲に当てはめて繰り返すことを再帰といいます。

たとえるなら、クラスを「160cm未満」と「160cm以上」の2組に分け、それぞれの組をまた基準を決めて半分に分けていくやり方です。最後は1人ずつになり、全員が身長順に並びます。

flowchart TD
  A["5, 3, 8, 1, 9, 2（基準値 5）"] --> B["5より小さい: 3, 1, 2"]
  A --> C["5"]
  A --> D["5より大きい: 8, 9"]
  B --> E["さらに基準値を選んで分割 → 1, 2, 3"]
  D --> F["さらに分割 → 8, 9"]

• 平均すると速い整列法です（計算量は n log n に比例。計算量とは、データ数 n が増えたとき手間がどれだけ増えるかの目安）。
• 基準値が毎回端の値になると、分割が偏って遅くなります（最悪は n² に比例）。そのため、前半と後半が同じくらいの大きさになる基準値を選ぶのが望ましいとされます。

マージソートとの見分け方：クイックソートは「先に大小で分ける」方法で、合体の操作はありません。マージソートは「とにかく半分に分け、整列しながら併合する」方法です。説明文に「併合」とあればマージソート、「基準値」とあればクイックソートです。

バブルソート：隣どうしの比較と交換

バブルソートは、隣り合う2つを比べて、順番が逆なら入れ替えます。これを端から端まで1回行うことを1パスと呼びます。泡（バブル）が水面に浮かぶように、値が1つずつ端へ運ばれるのが名前の由来です。

1パス後に何が決まるかは、走査の向きで決まります。

大きい値は交換のたびに後ろへ運ばれるので、先頭から走査すると最大値が末尾まで運ばれます。逆に末尾から走査すると、小さい値が前へ運ばれて最小値が A[1] に来ます。擬似コード（プログラムを日本語風に書いたもの）の問題では、内側ループの変数が n から減っていくか、増えていくかをまず確認しましょう。

選択ソート：比較回数は n(n−1)/2

選択ソートは、未整列部分から最小値（大きい順なら最大値）を探し、未整列部分の先頭と交換します。これを繰り返すと、先頭から順に確定していきます。

比較回数は、データの並び方に関係なく次のとおりです。

• 1回目：残り n 個から探すので n−1 回比較
• 2回目：n−2 回 … 最後は 1 回
• 合計：(n−1)+(n−2)+…+1 = n(n−1)/2

例：n=5 なら 4+3+2+1 = 10 で、5×4÷2 = 10 と一致します。迷ったら n=2 や n=3 を代入して確かめると確実です（n=3 なら比較は2回+1回=3回で、3×2÷2 = 3）。

シェルソートと基数ソート：手順を追う問題

シェルソートは、挿入ソートの改良版です。まず離れた間隔 H ごとの部分列を挿入法で整列し、H を小さくしながら繰り返し、最後は H=1（ふつうの挿入ソート）で仕上げます。遠くの要素を先に大まかに動かしておくので、最後の挿入ソートの手間が少なくて済みます。

基数ソートは、大小の比較をしません。代わりに、1の位の数字で0〜9のグループに分けて並べ直し、次に10の位で同じことをする、と下の桁から順に処理します。グループの中では前の順番を崩さないのがルールで、これがあるから最後の桁まで処理すると全体が整列します。

どちらの問題も、問われているのは「途中でどうなるか」です。最後まで整列が終わった答え（きれいに並んだ選択肢）に飛びつかず、問題が指定した手順のところで止めましょう。