整列（ソート）（sorting）

分類

テクノロジ系 アルゴリズムとプログラミング

出る試験

基本情報応用情報

重要度

★★★★☆

もう少し詳しい説明

整列（ソート）は、データを決まった順序に並べ替えることです。

なぜ並べ替えを行うのかというと、さまざまな処理を速くするためです。二分探索（真ん中と比べて探す範囲を半分ずつ捨てる方法）は整列済みでなければ使えませんし、同じ値をまとめて数えるのも、並んでいれば1回通るだけで済みます。並べ替えそのものが目的ではなく、その後の処理のために行います。

大事なのは、どの方法を使うかで処理時間が大きく変わることです。

まずは単純な3つ（O(n²)）

仕組みが単純なかわりに遅いグループです。名前と動きの対応がそのまま問われます。

バブルソートを1回分だけ追ってみます。

隣どうしを左から順に比べ、大きいほうを右へ送ります。1回通すと、いちばん大きい値が右端まで運ばれて確定します。泡（バブル）が浮かび上がるように値が移っていくので、この名前が付いています。

これを、確定していない範囲について繰り返します。あとでマージソートと比べられるように、同じ8件で最後まで数えてみます。

8 3 5 1 9 2 7 4 を並べ替えます。

7巡かかりました。 右端から1つずつ確定していくので、巡の数は件数より1つ少ない n − 1 回です。そして毎回、確定していない残り全部を見ています。

n 件を、n 回近くくり返し見る。 したがって全体では n × n、つまり O(n²) になります。

速いグループ（O(n log n)）：マージソート

マージソートは、データを半分ずつに分けていき、最後に合体させながら並べ直す方法です。

実際に8件を並べ替えてみます。

3段で終わりました。 そして 2³ ＝ 8、つまり log₂8 ＝ 3 です。件数が16件なら4段、32件なら5段。件数を2倍にしても、段は1つしか増えません。

各段では、8件すべてを1回ずつ見ています。よって全体で、

8件 × 3段 ＝ 24回

これが「n log n」の正体です。 n が横（1段あたりの件数）、log n が縦（段の数）。掛けているだけです。

7巡か、3段か

同じ8件を、2つの方法で並べ替えました。くり返した回数が違います。

1巡（1段）あたりに見るのは、どちらも8件ぶんです。 違うのは、それを何回くり返すか。

件数を増やすと、この差がはっきりします。

片方は件数と同じだけ増え、もう片方は20で済みます。

「くり返しが n 回か、log n 回か」。 2つのグループを分けているのは、この一点です。

クイックソート：平均は速いが、例外がある

クイックソートは、基準となる値（ピボット）を1つ決めて、それより小さい組と大きい組に分けることを繰り返します。うまく半分ずつに分かれれば、マージソートと同じく3段で片づきます。平均では O(n log n) で、実際にとても速い方法です。

ただし注意点があります。基準の選び方が悪いと、分けたつもりが片側に偏ります。

片側が0件だと、1回で1件しか減りません。 そうなるのは、すでに並び終わっている列の、先頭を基準にしたときです。1 2 3 4 5 6 7 8 の 1 を基準にすると小さい組は0件、次に 2 を基準にしても0件……と続きます。

結果、3段で済むはずが7段。バブルソートの7巡と同じ回数です。くり返しが log n 回ではなく n 回になってしまうので、いちばん回数が多くなる場合は、遅いグループと同じ O(n²) の伸び方に落ちます。

「もう並んでいるデータがいちばん遅い」。 クイックソートのいちばん意外なところで、応用情報ではここが問われます。「クイックソートは常に速い」と書かれた選択肢は誤りです。

なお、この「最大」のことを、試験の問題文や参考書では最悪の場合（最悪計算量）と書きます。言葉は強いのですが、いちばん運が悪かったときの回数という意味しかありません。

安定な整列

もう1つ、応用情報で問われる性質があります。

同じ値が複数あったとき、元の並び順が保たれる整列を、安定（stable）であるといいます。

たとえば「点数」で並べ替えるとき、同じ80点のAさんとBさんが元の順（A→B）のまま残れば安定、入れ替わる可能性があれば安定ではありません。

名簿を「クラス順に並べてから、点数順に並べ直す」といった二段階の並べ替えをするとき、安定かどうかが効いてきます。

どれを選ぶか

件数が少ないなら、単純な方法で十分です。O(n²) と O(n log n) の差が、どこから効いてくるのかを数で見ます。

8件なら3倍しか違いません。 手間をかけて速い方法を使うほどの差ではない、ということです。差が効いてくるのは件数が千、万と増えてからで、百万件では5万倍になります。

（この表の数は伸び方をくらべるための目安で、実際に数えた回数そのものではありません。実際の回数は方法ごとに違いますが、件数が増えたときの開き方は変わりません）

ほとんど並んでいるデータを仕上げるだけなら、挿入ソートが速いこともあります。

件数が多いなら 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²)

安定な整列

同じ値どうしの元の並び順が、並べ替えた後も保たれる性質

ミニクイズ

この分野をまとめて解く → アルゴリズムとプログラミングのミニテスト（全44問）

最終更新：2026-09-29