整列（ソート）（sorting）
- テクノロジ系
- アルゴリズムとプログラミング
- 基本情報
- 応用情報
- 重要度 ★★★★☆
データを決まった順序に並べ替えること。方法によって処理時間の伸び方が大きく違う。
もう少し詳しい説明
整列（ソート）は、データを決まった順序に並べ替えることです。
なぜ並べ替えを行うのかというと、さまざまな処理を速くするためです。二分探索は整列済みでなければ使えませんし、同じ値をまとめて数えるのも、並んでいれば1回通るだけで済みます。並べ替えそのものが目的ではなく、その後の処理のために行います。
大事なのは、どの方法を使うかで処理時間が大きく変わることです。
まずは単純な3つ（O(n²)）
仕組みが単純なかわりに遅いグループです。名前と動きの対応がそのまま問われます。
| 名前 | 何をするか |
|---|---|
| バブルソート | 隣どうしを比べて、順序が逆なら入れ替える |
| 選択ソート | 未整列の中からいちばん小さいものを選んで、前に置く |
| 挿入ソート | 整列済みの列に、次の1件を正しい位置へ差し込む |
バブルソートを1回分だけ追ってみます。
隣どうしを左から順に比べ、大きいほうを右へ送ります。1回通すと、いちばん大きい値が右端まで運ばれて確定します。泡（バブル）が浮かび上がるように値が移っていくので、この名前が付いています。
これを、確定していない範囲について繰り返します。n 件なら、n 回近く繰り返し、1回ごとに n 件近く比べるので、全体では n × n、つまり O(n²) になります。
速い2つ（O(n log n)）
マージソートは、データを半分ずつに分けていき、最後に合体させながら並べ直す方法です。段の数が log₂n、各段で全 n 件を扱うので、O(n log n) になります。
クイックソートは、基準となる値（ピボット）を1つ決めて、それより小さい組と大きい組に分けることを繰り返します。平均では O(n log n) で、実際にとても速い方法です。
ただしクイックソートには注意点があります。基準の選び方が悪いと、分けたつもりが片側に偏り、いちばん回数が多くなる場合には O(n²) まで落ちます。「クイックソートは常に速い」と書かれた選択肢は誤りです。
| 平均 | 最大（いちばん回数が多いとき） | |
|---|---|---|
| マージソート | O(n log n) | O(n log n) |
| クイックソート | O(n log n) | O(n²) |
| ヒープソート | O(n log n) | O(n log n) |
なお、この「最大」のことを、試験の問題文や参考書では最悪の場合（最悪計算量）と書きます。言葉は強いのですが、いちばん運が悪かったときの回数という意味しかありません。
安定な整列
もう1つ、応用情報で問われる性質があります。
同じ値が複数あったとき、元の並び順が保たれる整列を、**安定（stable）**であるといいます。
たとえば「点数」で並べ替えるとき、同じ80点のAさんとBさんが元の順（A→B）のまま残れば安定、入れ替わる可能性があれば安定ではありません。
| 安定 | 安定ではない |
|---|---|
| バブルソート、挿入ソート、マージソート | 選択ソート、クイックソート、ヒープソート |
名簿を「クラス順に並べてから、点数順に並べ直す」といった二段階の並べ替えをするとき、安定かどうかが効いてきます。
どれを選ぶか
件数が少ないなら、単純な方法で十分です。O(n²) と O(n log n) の差は、件数が大きくなって初めて効いてきます。ほとんど並んでいるデータを仕上げるだけなら、挿入ソートが速いこともあります。
件数が多いなら O(n log n) のグループを使います。安定さが必要ならマージソート、速さを優先するならクイックソート、という選び方になります。
覚え方：2つのグループに分けるだけ
試験で問われるのは、ほとんどがグループ分けです。
- 遅いグループ O(n²) … バブル・選択・挿入（単純な3つ）
- 速いグループ O(n log n) … マージ・クイック・ヒープ（分けて片づけるグループ）
そのうえで、クイックソートは最大で O(n²) と、選択ソートとクイックソートは安定ではない。この2つの例外を足せば、出題される範囲は押さえられます。
試験ではこう出る
科目A（旧・午前）のアルゴリズム分野で頻出です。多いのは、整列方法の名前と動きを結び付けさせる問題と、計算量を選ばせる問題です。バブルソートの途中経過を示して「何回目の走査か」を答えさせる形も出ます。応用情報では、安定かどうかや、クイックソートの回数が最大になる条件まで踏み込みます。
途中経過を追う問題は、1回の走査で何が確定するかを先に押さえてください。バブルソートなら右端に最大値、選択ソートなら左端に最小値が確定します。確定した側がどちらかが分かれば、示された配列がどの方法の途中かを見分けられます。
関連する用語
- 計算量
- 件数が増えたときの処理時間の伸び方。整列の方法を比べる物差しになる
- 二分探索
- 並んでいるデータを半分ずつ絞る探し方。整列が済んでいることが前提
- バブルソート
- 隣どうしを比べて入れ替える、いちばん単純な方法。計算量は O(n²)
- マージソート
- 半分に分けてから合体させる方法。計算量は O(n log n)
- クイックソート
- 基準値より大きい組と小さい組に分けていく方法。平均は速いが、最大では O(n²)
- 安定な整列
- 同じ値どうしの元の並び順が、並べ替えた後も保たれる性質
ミニクイズ
整列アルゴリズムのうち、平均計算量が O(n log n) であるものはどれか。
正解は 4番：マージソート
マージソートは、データを半分ずつに分けてから順に合体させていく方法で、段の数が log₂n、各段で全 n 件を扱うため、計算量は O(n log n) になります。バブルソート・選択ソート・挿入ソートの3つは、平均でも最大でも O(n²) です（挿入ソートは、すでにほとんど並んでいる場合にかぎり O(n) まで速くなります）。この3つが遅いグループ、マージソートとクイックソート（平均）が速いグループ、という2つに分けて覚えるのが、出題への近道です。
最終更新：2026-09-23