13　ソート（バブル・選択）

「並び替え（ソート）」はコンピュータが最もよく使う処理の一つ。

成績順・価格順・関連度順……日常のシステムの裏側では必ずソートが動いています。

この章では最も直感的なソートである選択ソートを中心に学びます。 コードの細かいトレースは練習問題で扱うので、まずは「どんな動きか」をしっかりイメージしましょう。
この資料では配列の要素番号は1から始まるものとします。 並び替えの方向は昇順（小さい順）を基本とします。

1. 選択ソート

未整列部分の中から最小値を探して、先頭と交換する操作を繰り返します。 毎回「最小値を選択（select）する」ことからこの名前がついています。

1パスでやること：
① 未整列部分の最小値を探す（内側ループで全部チェック）
② その最小値を未整列部分の先頭と交換する（1回だけ）

動きのイメージ（{5, 3, 4, 1, 2} を昇順に）

確定済み 最小値（交換対象） パス1：未整列全体の最小値=1（[4]）を先頭[1]と交換 1 3 4 5 2 → {1, 3, 4, 5, 2} パス2：残り{3,4,5,2}の最小値=2（[5]）を[2]と交換 1 2 4 5 3 → {1, 2, 4, 5, 3} （パス3以降も同様…） 最終結果： 1 2 3 4 5

コード

○ selection_sort(整数型の配列: a)
    整数型: i, j, min_idx, tmp
    整数型: n ← a の要素数

    for ( i を 1 から n - 1 まで 1 ずつ増やす )
        min_idx ← i                    // 未整列部分の先頭を暫定最小とする
        for ( j を i + 1 から n まで 1 ずつ増やす )
            if ( a[j] が a[min_idx] より小さい )
                min_idx ← j            // より小さい要素が見つかれば位置を更新
            endif
        endfor
        // min_idx の要素を先頭（i）と交換
        tmp        ← a[i]
        a[i]       ← a[min_idx]
        a[min_idx] ← tmp
    endfor
コードを読むポイント：
min_idx は「最小値の位置（添字）」を覚えておく変数です。 最小値の値ではなく位置を記録し、1パス終了後に1回だけ交換するのが選択ソートの特徴です。

2. バブルソートをざっくり紹介

バブルソートは 隣り合う要素を比べ、大きい方を右へ移動させる ことを繰り返すソートです。 1回のパスで最大値が末尾に「泡（バブル）のように浮き上がる」ことが名前の由来です。

選択ソートが「最小値を先頭に持ってくる（1パス1交換）」のに対して、 バブルソートは「最大値を末尾に押し出す（比較のたびに交換が起きる）」イメージです。

どちらも2重ループで動き、計算量は O(n²) で同じです。
見分け方：a[j] と a[j+1] の隣接比較・交換があればバブル、 min_idx で最小値の位置を探していれば選択ソートです。

3. 計算量とまとめ

ソート動きのイメージ1パスの交換計算量
選択ソート最小値を探して先頭へ1回O(n²)
バブルソート隣を比べて大きい方を右へ複数回O(n²)
O(n²) の実感：
比較回数 ≈ n²/2 なので、n=100 なら約 5,000 回、n=1,000 なら約 50 万回です。 データ量が増えると急激に遅くなります。次の章では O(n log n) の高速なソートを学びます。

4. 理解度チェック問題

問題13-1

選択ソートで「1パスごとに行う操作」はどれか。

解説を表示 正解：イ
選択ソートは未整列部分から最小値を探して先頭と交換します。
ア（隣同士の比較と交換）はバブルソートの動きです。ウ（最大値を先頭へ）は逆向きになってしまいます。 エ（2分割 + 再帰）はマージソート・クイックソートのアプローチで、この章の範囲外です。

問題13-2

選択ソートで {5, 3, 4, 1, 2} を昇順に並び替えるとき、パス1（i=1）終了後の配列はどれか。

解説を表示 正解：ウ
未整列全体 {5,3,4,1,2} の最小値は 1（位置4）。これを先頭（位置1）の 5 と交換 → {1, 3, 4, 5, 2}。
ア（先頭2個だけ交換）はバブルの1ステップ的な誤りです。イ（完成形）はパス1だけで全体が整列するわけではありません。

問題13-3

次の選択ソートのコードで、変数 min_idx の役割として正しいものはどれか。

min_idx ← i
for ( j を i + 1 から n まで 1 ずつ増やす )
    if ( a[j] が a[min_idx] より小さい )
        min_idx ← j
    endif
endfor
解説を表示 正解：ウ
min_idx ← j は「最小値の位置（添字）」を記録しています。値ではなく位置を覚えるのがポイントです。
最後に a[i] と a[min_idx] を交換するために位置が必要です。 min_idx ← i と初期化されていることから、ア（パス番号）やエ（回数）ではないと分かります。

問題13-4

次のコードはバブルソートと選択ソートのどちらか。

for ( i を 1 から n - 1 まで 1 ずつ増やす )
    min_idx ← i
    for ( j を i + 1 から n まで 1 ずつ増やす )
        if ( a[j] が a[min_idx] より小さい )
            min_idx ← j
        endif
    endfor
    tmp ← a[i]
    a[i] ← a[min_idx]
    a[min_idx] ← tmp
endfor
解説を表示 正解：イ
min_idx で最小値の位置を記録し、内側ループが終わってから1回だけ交換する構造が選択ソートの特徴です。
ウ（マージソート）は明らかに違います。ア・エ（バブルソート）は誤りで、バブルの特徴は 隣接する a[j] と a[j+1] を比べてループ内で交換することです。 このコードには隣接比較も内側での交換もありません。

発展問題（FE試験スタイル）

ここからは応用問題です。 使う知識はこれまでに学んだもの（選択ソート、二重ループ）だけです。 これは基本情報技術者試験（FE）の科目B でよく出る形です。

発展問題13-A

配列 a = {4, 2, 7, 1, 5} に対して選択ソート（昇順）を実行する。
外側ループ 1 回目（i=1）が終わった直後の配列はどれか。

for ( i を 1 から n - 1 まで 1 ずつ増やす )
    min_idx ← i
    for ( j を i + 1 から n まで 1 ずつ増やす )
        if ( a[j] が a[min_idx] より小さい )
            min_idx ← j
        endif
    endfor
    tmp ← a[i]
    a[i] ← a[min_idx]
    a[min_idx] ← tmp
endfor
解説を表示 正解：ウ
i=1 のとき、未整列部分は {4,2,7,1,5} 全体。内側ループで最小値の位置を探す：
・min_idx=1（a[1]=4）から開始
・j=2: a[2]=2 < a[1]=4 → min_idx=2
・j=3: a[3]=7 < a[2]=2? False
・j=4: a[4]=1 < a[2]=2 → min_idx=4
・j=5: a[5]=5 < a[4]=1? False
最小値は a[4]=1。a[1]=4 と a[4]=1 を交換 → {1, 2, 7, 4, 5}
ア（完成形に近い）は外側1回で全部並ぶわけではない。 イ（先頭2個を交換）はバブルの1ステップ的な誤り。エ（降順）は明らかに違う。

発展問題13-B

要素数 n=100 の配列に対して選択ソートを行うとき、
配列の比較はおよそ何回行われるか。

解説を表示 正解：ウ
選択ソートは「未確定の中から最小値を選ぶ」を n-1 回繰り返す。
比較回数：(n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2
n=100 なら 100 × 99 / 2 = 4,950 回 ≒ 約 5,000 回。これが O(n²) の正体。
ア（n回）は1重ループ相当。イ（2n回）は過小評価。エ（約 n⁴ 相当）はありえない量。