整列（選択ソート・交換ソート・挿入ソート）の違いと比較回数

こんにちは、数強塾代表の藤原進之介です。この記事は参考書『藤原進之介の最強120講義』の第56講「整列（選択ソート・交換ソート・挿入ソート）」のWeb版です。共通テスト「情報Ⅰ」での重要度はA（頻出。得点差がつく）、情報Ⅱでの接続先は(4)情報システムとプログラミングです。

整列（ソート）は「選択ソートは最小値を探して先頭と交換、バブルソートは隣どうしを比べて交換、挿入ソートは差し込む」と3つの手順を丸暗記して終わりにされがちな分野です。しかしそれでは、共通テストが必ず仕掛けてくる「途中経過の配列を選べ」「比較回数を数えよ」「プログラムの空欄を埋めよ」の3つに太刀打ちできません。この講では3つの違いを「1周ごとに何を確定させているか」という1本の軸に還元し、実際にPythonで動かして比較回数と交換回数を数えます。

1. この講の問い

3つの整列法は、1回のパスで「何を確定させている」のかが違う。それは何か。

2. 結論

3. なぜそうなるのか

3-1. なぜ整列するのか（探索が借りていた前提を、この講が作る）

第55講で二分探索を扱いました。二分探索は「真ん中を見て、探す値より大きければ右半分を丸ごと捨てる」という手続きです。この「丸ごと捨てる」が成立するのは、配列が並んでいるからです。 並んでいなければ、真ん中の値が何であろうと、右半分に探す値が無いとは言えません。

国の教材もそこを明記しています。

つまり二分探索は速さを「借りている」。その借金を返す作業が整列です。 だから整列は探索の付属物ではなく、探索の前提を作る側の主役だと考えてください。

3-2. 比較回数 n(n−1)/2 は公式ではなく「組み合わせの数」

整列の比較回数としてよく出てくる n(n−1)/2 を、公式として覚えてはいけません。これは総当たりの組み合わせの数そのものです。

n 個の要素から2つを選ぶ組み合わせは、1個目に n 通り・2個目に n−1 通り、ただし (A, B) と (B, A) は同じ組なので2で割って n(n−1)/2。n = 8 なら 8 × 7 ÷ 2 = 28。これは「8個の中から2つを選ぶ選び方が28通りある」という、ただの数え上げです。

では、なぜ整列の比較回数がこの数になるのか。 選択ソートで考えます。1周目は先頭以外の n−1 個と比べ、2周目は n−2 個、…、最後は1個。合計は

(n−1) + (n−2) + … + 2 + 1 = n(n−1)/2

1から n−1 までの和なので、やはり n(n−1)/2 です。つまり「全部の組をちょうど1回ずつ比べた」ことと同じ回数になっている。 選択ソートは、あらゆる2要素の組を過不足なく1回ずつ比較しているのです。公式を覚える必要はなく、「全部の組を1回ずつ」と思い出せば毎回その場で導けます。

交換（バブル）ソートも、打ち切りをしなければ内側ループの形が同じなので同じ n(n−1)/2 回。挿入ソートだけは最悪のときにしかこの回数になりません。ここが得点差の出るところです。

3-3. 選択ソート ── 位置を1つずつ確定させる

手順：まだ整列していない部分から最小値を探し、その部分の先頭と入れ替える。これを繰り返す。

確定しているもの：1周ごとに、配列の先頭から i 番目までが最終的な答えと同じになります。i 番目に入った値はもう二度と動きません。

なぜ交換が少ないのか：1周のあいだ、コンピュータは最小値の「添字だけ」を覚えておきます。実際に値を動かすのは1周につき1回だけ。だから交換回数は最大でも n−1 回です。値の移動コストが高いとき（大きなデータのかたまりを動かすとき）に有利になります。

弱点：入力がどうであれ比較回数は必ず n(n−1)/2。すでに完全に並んでいても最後まで全部比べます。手を抜くしくみが原理的に無いのです。

3-4. 交換（バブル）ソート ── 大きい値が端へ浮き上がる

手順：隣どうしを比べ、順序が逆なら入れ替える。左から右へ1往復させる。これを繰り返す。

確定しているもの：1周ごとに末尾から数えて i 番目までが確定します。1周目が終わると、配列全体の最大値が必ず右端に到達しています。理由は単純で、最大値はどの相手と比べても必ず「自分のほうが大きい」ので、出会うたびに右へ押し出されるからです。泡が水面に浮くように見えるのでバブルソートと呼ばれます。

なぜ交換が多いのか：値を1マスずつしか動かせないからです。左端にある小さい値を右端の正しい位置まで運ぶには n−1 回の交換が要ります。選択ソートが「添字を覚えて最後に1回だけ動かす」のに対し、バブルソートは毎回律儀に動かす。ここが決定的な差です。

唯一の長所：1周まわって一度も交換が起きなかったら、その時点で整列が完了していると分かります。この早期打ち切りを入れると、すでに整列済みの配列を n−1 回の比較だけで終えられます。3つの中で「終わったことに自分で気づける」のはバブルソートだけです。

3-5. 挿入ソート ── 手札を並べるのと同じ

手順：左端の1枚を「整列済み」とみなす。2枚目を取り、整列済みの列の正しい位置に差し込む。3枚目、4枚目と続ける。トランプの手札を整理するときに私たちが無意識にやっている操作そのものです。

確定しているもの：左側 i 枚が互いに整列しているという状態。ただし選択ソートと違い、この i 枚が最終的な答えとは限りません。あとから小さい値が来れば割り込まれます。確定しているのは「順序」であって「位置」ではない。 ここが3つを見分ける決め手になります。

なぜほぼ整列済みに強いのか：差し込む値が、整列済みの列の右端の値以上なら、1回比べただけで「ここでよい」と分かって止まれるからです。完全に整列済みの配列なら比較は n−1 回で終わります。n = 1000 なら999回。選択ソートの499,500回と比べて500分の1です。

弱点：逆順のときは毎回いちばん左まで押し込むので、比較も移動も n(n−1)/2 回。3つの中で最悪ケースがいちばん重くなります。

3-6. 「毎回何を確定させているか」で並べ直す

この表を頭に入れれば、3つの手順を暗記する必要が消えます。「選択は位置を左から確定」「交換は位置を右から確定」「挿入は順序を左へ広げる」。途中経過の配列を選ばせる問題は、この一言だけで解けます。

3-7. 交換回数の正体は「転倒数」

交換ソートの交換回数と、挿入ソートの移動回数は、実は必ず同じ数になります。その数は「左にあるのに右より大きい」ペアの個数（転倒数）です。

隣どうしの1回の交換で、逆になっているペアはちょうど1組だけ解消されます。だから逆順ペアが全部で16組あれば、交換は16回必要。挿入ソートで値を1マスずらす操作も、同じく1組ずつ解消しています。「隣どうししか動かさないアルゴリズムの手数は、入力の乱れ具合そのもの」なのです。

配列 [7, 3, 9, 1, 8, 2, 6, 4] で数えてみます。7より右で7未満なのは 3, 1, 2, 6, 4 の5個。3より右で3未満は 1, 2 の2個。9より右で9未満は 1, 8, 2, 6, 4 の5個。1は0個。8より右で8未満は 2, 6, 4 の3個。2は0個。6より右で6未満は 4 の1個。合計 5 + 2 + 5 + 0 + 3 + 0 + 1 = 16。あとで実測値と一致することを確認します。

3-8. 安定性 ── 同点の生徒の順番が入れ替わる

同じ値が複数あるとき、元の並び順が保たれるアルゴリズムを「安定」といいます。名簿をクラス順に並べたあと点数順に並べ直したとき、同じ点数の中でクラス順が保たれていてほしい。安定なソートならそれが成り立ちます。

選択ソートは安定ではありません。 遠くにある最小値と先頭を「ジャンプして」交換するので、そのあいだにある同値の要素を飛び越してしまうからです。交換ソートと挿入ソートは隣どうししか動かさないので安定です。次の節で実際に確かめます。

4. 手で確かめる

配列 a = [7, 3, 9, 1, 8, 2, 6, 4]（n = 8）を、3つの方法で整列させます。n(n−1)/2 = 8 × 7 ÷ 2 = 28。まず図で見てください。青いマスが「確定した部分」です。

4-1. 3つの整列を図で並べる

左から青が伸びていきます。1マス確定するごとに、そのマスは二度と動きません。

今度は右から青が伸びます。パス1で9が右端へ、パス2で8がその隣へ。大きい値から順に浮き上がっているのが見えます。なお4周目でもう並び終わっているのに、打ち切りが無ければ7周目まで回ります。

青い部分は「互いに整列済み」というだけで、最終形とは限りません。パス3で1が割り込み、青い部分の中身がまるごと右にずれています。選択ソートの青とは意味が違うことを、ここで確認してください。

4-2. 比較回数と交換回数を数える

同じ3つを、累計の比較回数・交換回数つきで並べます。

パス2に注目してください。 9は7以上なので1回比べただけで止まっています。比較が1回しか増えていない。これが挿入ソートの「手抜き」のしくみです。

4-3. Python で実装して計測する

次のコードは実際に実行して出力を確認したものです。手元にPython 3があれば、そのまま貼り付けて動きます。

def selection_sort(a):          # 選択ソート
    a = a[:]; cmp = swp = 0; n = len(a)
    for i in range(n - 1):
        mi = i                          # 最小値の「添字」だけ覚えておく
        for j in range(i + 1, n):
            cmp += 1
            if a[j] < a[mi]: mi = j
        if mi != i:                     # 交換は1周に1回だけ
            a[i], a[mi] = a[mi], a[i]; swp += 1
    return a, cmp, swp
# ------------------------------------------------------------
def bubble_sort(a, early=False):    # 交換（バブル）ソート
    a = a[:]; cmp = swp = 0; n = len(a)
    for i in range(n - 1):
        moved = False
        for j in range(n - 1 - i):
            cmp += 1
            if a[j] > a[j + 1]:         # 隣どうししか動かさない
                a[j], a[j + 1] = a[j + 1], a[j]; swp += 1; moved = True
        if early and not moved: break   # 1周無交換なら整列完了
    return a, cmp, swp
# ------------------------------------------------------------
def insertion_sort(a):              # 挿入ソート
    a = a[:]; cmp = mov = 0
    for i in range(1, len(a)):
        x = a[i]; j = i - 1
        while j >= 0:
            cmp += 1
            if a[j] > x:
                a[j + 1] = a[j]; mov += 1; j -= 1
            else:
                break                   # ここで止まれるのが挿入ソートの強み
        a[j + 1] = x
    return a, cmp, mov

この3つに、①ランダム ②ほぼ整列済み ③逆順 の3ケース（＋比較用に完全整列済み）を通した結果です。「交換＋打切」は早期打ち切りを入れた交換ソートです。

n を1000に増やすと差が露骨になります。n(n−1)/2 = 499,500 です。

④は第55講（線形探索と二分探索）の結論とまったく同じ形です。「二分探索が常に速いわけではない」のと同じ理由で、「挿入ソートが常に速いわけでもない」。アルゴリズムに絶対の優劣は無く、あるのは入力との相性だけ──これは情報Ⅰで最も重要な考え方のひとつです。

4-4. 国の教材のコードを実際に動かしてみる

文部科学省「情報Ⅰ」教員研修用教材 第3章 学習15 には、選択ソートのプログラム例（図表9）が載っています。ここで注意してほしいことがあります。このコードは、私が3-3で説明した「最小値の添字を覚えて1周に1回だけ交換する」型ではありません。 内側のループで小さい値を見つけるたびに、その場で入れ替えています。

そして教材の演習3は、まさにここを見せる設計になっています。

教材は答えを載せていません。そこで私が実際に実行して数えました。対象は教材が指定している17個の配列です。

比較回数は完全に同じ136回（＝ 17 × 16 ÷ 2）。違うのは交換回数だけで、約6.6倍です。 n = 1000 のランダム列で比べると 245,331回 対 991回、逆順1000件では 499,500回 対 500回になりました。

これは教材の誤りではありません。「同じ『選択ソート』という名前でも、交換をどこに置くかで手数が桁で変わる」ことを、演習として体験させる作りだと私は読みました。 そして共通テストのプログラム穴埋めで問われるのは、まさにこの「どこで交換するか」です。

4-5. 安定性を確かめる

(点数, 名前) のペアを点数で昇順に並べます。入力は [(30, A), (10, B), (30, C), (20, D)]。同点の A と C がどうなるかを見てください。

選択ソートだけ、同点の A と C の順番がひっくり返っています。 遠くの値とジャンプして交換するからです。

5. 共通テストではこう出る

重要度 A（頻出。得点差がつく）。整列そのものが主題になる年もあれば、部品として紛れ込む年もあります。

5-1. 出題される3つの型

型1：途中経過の配列を選ばせる
「この配列に交換法を2回適用したときの状態として正しいものを選べ」という形です。3-6の表があれば即答できます。選択なら左から確定、交換なら右から確定。選択肢を見て、確定しているべき側が確定していないものを消すだけで大半が落ちます。

型2：比較回数・交換回数を数えさせる
「n個のデータに対して比較は何回行われるか」。ここで n(n−1)/2 を公式として暗記していると、内側ループの範囲を変えられた瞬間に崩れます。(n−1) + (n−2) + … + 1 と書き下す習慣をつけてください。

型3：プログラムの穴埋め
いちばん配点が大きい型です。ループの範囲（i+1 か i か）、比較の向き（小なりか大なりか）、交換の位置（内側ループの中か外か）が空欄になります。4-4で見たとおり、交換の位置を1段変えるだけで交換回数が桁で変わります。 意味を理解していないと選べません。

5-2. センター自身の言葉で確認する

大学入試センターが公表した試作問題『情報』の概要には、第3問 問3のねらいがこう書かれています。

「繰返しや条件分岐を用いて最小値を求めるアルゴリズム」は、選択ソートの内側そのものです。 整列という名前で出題されなくても、その部品は出ます。ここが重要度Aの根拠です。

5-3. 記述に使う文法（共通テスト用プログラム表記）

センターの例示資料で直接確認できる文法は次のとおりです（私が2026年8月3日に原本PDFで確認しました）。

• 繰返しは2種類。「x を 0 から 9 まで 1 ずつ増やしながら繰り返す:」と「n < 10 の間繰り返す:」。前者には「減らしながら」もある
• 配列名は先頭文字が大文字（Tokuten[3]、Data[2,4]）。添字は特に説明がなければ0から
• 制御範囲は縦線と鉤線で表し、鉤線が制御文の終わりを示す
• 「Tokutenのすべての値を0にする」という一括代入の書き方がある

ただしセンター自身が「問題文の記述を簡潔にするなどの理由で，この説明文書の記述内容に従わない形式で出題することもあります」と明記しています。書式を暗記するのではなく、当日の問題文の説明を読む。 これが正しい構えです（詳しくは第48講 変数と代入と第47講 アルゴリズムと流れ図を参照してください）。

5-4. 引っかかりやすいところ

• 交換に一時変数が要ることを忘れる。 a[i] = a[j] を先に書くと a[i] の値が消えます。空欄3行を並べ替えさせる出題は、ここを突いています
• 添字の範囲。 内側ループを i から始めると、自分自身と比べることになります
• 「n(n−1)/2 回」を最悪値ではなく常に成り立つ値だと思い込む。 挿入ソートは違います
• 早期打ち切りの有無。「交換が起きなかったら終了」が付いているかどうかで答えが変わります

なお、途中経過を1行ずつ書き出す作業そのものは第54講 トレースで扱った技術です。本講はその技術を整列に適用しています。

6. 情報Ⅱではこうなる

6-1. まず制度上の事実を押さえる

学習指導要領（平成30年告示）解説 情報編の全文で「整列」という語は2か所にしか出てきません（私が2026年8月3日にPDF全文を検索して確認しました）。1つ目は情報Ⅰ(3)の学習活動例です。

2つ目は共通教科ではなく、専門学科の教科「情報」の科目「情報システムのプログラミング」にあります。

そして「情報Ⅱ」の側には「整列」が1件もありません。 これは重要な事実です。整列は情報Ⅰで扱って終わりの項目ではなく、情報Ⅱでは名前が消えて、別のものの内側に埋め込まれるのです。

さらに、国の「情報Ⅰ」教員研修用教材 第3章の全文にも、「挿入ソート」「バブルソート」「交換法」「選択法」という語は1件もありません（同じく私が全文検索で確認）。国の教材が扱う整列は選択ソートとクイックソートの2つだけです。つまり、共通テスト対策で定番の交換法・挿入法は、国の一次資料の外にある。本書ではこれまでにトレース・サブネット・論理回路で同じ構造を見つけてきましたが、整列がその4つ目です。教科書と入試のほうが、国の教材より先へ行っている領域だと理解してください。

6-2. 情報Ⅱでは整列は「前処理の1行」になる

では情報Ⅱのどこに整列が現れるのか。文部科学省「情報Ⅱ」教員研修用教材 第3章 学習12「大量のデータの収集と整理・整形」の演習4に、こうあります。

演習4のコードは全部で5行。そのうち整列は1行です。 アルゴリズムの中身は一切書かれていません。情報Ⅰとの違いを表にします。

情報Ⅱでは「どう並べ替えるか」は問われません。「何を基準に並べ替えるか」だけが問われます。 ascending の一語を間違えれば、人口増減率が最も低い県を「最も高い県」として報告してしまう。間違いの意味が「プログラムが動かない」から「間違った結論を出す」へ変わるのです。

6-3. 整列は「重複を除く」「大量データを扱う」の下ごしらえになる

同じ学習12は、前処理として何をするかをこう列挙しています。

「重複するデータを除去する」に注目してください。 未整列の n 件から重複を探すなら、素朴には全部の組を見る n(n−1)/2 回が要ります。ところが整列してしまえば、同じ値は必ず隣どうしに並ぶので、隣を1回ずつ見るだけ（n−1 回）で済みます。

整列そのものにコストがかかっても、そのあとの操作がまとめて安くなる。整列は「1回払って何度も回収する」投資です。 これは第55講で見た「同じ配列を何度も探すなら整列したほうが得」と同じ構造です。教材はそこまでは書いていませんが、前処理の並び順を見ればそう読めます。

そして学習11には、規模が上がったときの話が書かれています。

「データをどう並べて置くか」が、そのままシステムの選択になっている。 情報Ⅰの整列が「配列を並べ替える手続き」だったのに対し、情報Ⅱでは「データをどの形で蓄えておくか」という設計判断に化けます。同じ教材は「データを扱うことに向いたこれらの言語ではRDBをSQLで直接操作するよりもずっと簡単に高速にデータを読み込み，適切な形で処理することができる」とも書いており、速さの議論の単位が「行数」から「道具の選択」へ上がっていることが分かります。

6-4. その先（資格試験・実務）

情報処理推進機構（IPA）「基本情報技術者試験（レベル2）シラバス Ver.9.2」では、整列は独立項目です。「（2）代表的なアルゴリズム ①整列・併合・探索のアルゴリズム」の用語例を、原文の並び順で書き出します。

整列が7種類、探索が3種類。 高校の教材が2種類（選択・クイック）しか挙げていないのに対して、資格試験のシラバスでは7種類が並びます。高校と実務のあいだの段差が、ここでも見えます。

そして高校の一次資料にはどこにも出てこない「計算量」「オーダー記法」が、このシラバスでは独立した項目になっています。本講で数えた n(n−1)/2 という具体的な数が、その入口です。

まとめ

• 3つの整列法の違いは手順ではなく1周で何を確定させるか。選択＝左から位置、交換＝右から位置、挿入＝左側の順序
• n(n−1)/2 は公式ではなく「n個から2個を選ぶ組み合わせの数」。(n−1) + (n−2) + … + 1 と書き下せば毎回導ける
• 交換ソートの交換回数と挿入ソートの移動回数は、どちらも入力の転倒数に一致する（実測でどちらも16回）
• ほぼ整列済みなら挿入ソートは選択ソートの約498分の1（n = 1000 で1,004回 対 499,500回）。逆順なら4方式とも499,500回で横並び
• 選択ソートは安定ではない。同点の順序が入れ替わる
• 国の教材が扱う整列は選択ソートとクイックソートだけ。交換法・挿入法は一次資料の外にある
• 情報Ⅱでは整列は前処理の1行になり、問われるのは「何を基準に、昇順か降順か」だけ。間違いの意味が変わる

出典（すべて2026年8月3日に取得）

• 文部科学省「高等学校学習指導要領（平成30年告示）解説 情報編」平成30年7月
• 文部科学省「高等学校情報科『情報Ⅰ』教員研修用教材」第3章 コンピュータとプログラミング（令和2年）
• 文部科学省「高等学校情報科『情報Ⅱ』教員研修用教材」第3章 情報とデータサイエンス 前半（令和2年）
• 大学入試センター「令和7年度大学入学共通テスト 試作問題『情報』の概要」2022年11月9日公表
• 情報処理推進機構（IPA）「基本情報技術者試験（レベル2）シラバス Ver.9.2」掲載 2026年1月8日

本講は『藤原進之介の最強120講義』の講義一覧の第56講です。制度の話は2026年8月時点の情報です。