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

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

成績順に並べる、商品を価格順に表示する、検索結果を関連度順に並べる—— 日常的に使っているシステムの裏側では、必ずと言っていいほどソートが動いています。

ソートアルゴリズムには多くの種類があり、それぞれ得意な場面が違います。 この資料では最も基本的なバブルソートと選択ソートを学びます。 どちらも仕組みはシンプルですが、コードを読んでトレースする練習が試験対策の核心です。
この資料では配列の要素番号は1から始まるものとします。 並び替えの方向は昇順（小さい順）を基本とします。

1. バブルソート

隣り合う要素を比較して、大きい方を右に移動させる操作を繰り返します。 1回のパスで最大値が末尾に「泡（バブル）のように浮き上がる」ことからこの名前がついています。

仕組みの図解（{5, 3, 4, 1, 2} を昇順に）

比較中 交換発生 確定（最大値が右端へ） パス1（i=1） j=1 5 3 4 1 2 5>3 → 交換 → {3,5,4,1,2} j=2 3 5 4 1 2 5>4 → 交換 → {3,4,5,1,2} j=3 3 4 5 1 2 5>1 → 交換 → {3,4,1,5,2} j=4 3 4 1 5 2 5>2 → 交換 パス1完了 → 5が末尾に確定 3 4 1 2 5 ← 確定 （パス2以降も同様に繰り返し…） 最終結果： 1 2 3 4 5

コード

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

    for ( i を 1 から n - 1 まで 1 ずつ増やす )
        for ( j を 1 から n - i まで 1 ずつ増やす )
            if ( a[j] が a[j + 1] より大きい )
                tmp    ← a[j]      // 隣り合う要素を交換
                a[j]   ← a[j + 1]
                a[j + 1] ← tmp
            endif
        endfor
    endfor
内側ループの終了値が n - i の理由：
パスを重ねるごとに末尾から確定済みの要素が増えます。 確定済みの部分は比較不要なので、内側ループの範囲を1ずつ狭めています。

2. 選択ソート

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

仕組みの図解（{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

3. 2つのソートの比較

項目バブルソート選択ソート
考え方隣り合う要素を比べて交換最小値を探して先頭と交換
交換のタイミング比較のたびに（多い）1パスに1回（少ない）
内側ループの役割隣接比較・交換最小値の位置を探す
共通点どちらも2重ループ。要素数 n に対して比較回数は約 n²/2 回
試験で問われるポイント： コードを見て「これはどちらのソートか」を判断する問題が出ます。 隣接比較（a[j] と a[j+1]）があればバブルソート、 最小値インデックス（min_idx）を持つのが選択ソートの特徴です。

4. 理解度チェック問題

問題13-1

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

解説を表示 正解：ア
j=1: 4>2 → 交換 {2,4,7,1,5}
j=2: 4<7 → そのまま {2,4,7,1,5}
j=3: 7>1 → 交換 {2,4,1,7,5}
j=4: 7>5 → 交換 {2,4,1,5,7}
パス1完了で最大値 7 が末尾に確定。

問題13-2

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

解説を表示 正解：ウ
未整列部分 {5,3,4,1,2} の最小値は 1（位置4）。これを先頭（位置1）の 5 と交換 → {1, 3, 4, 5, 2}。

問題13-3　空欄補充

次のバブルソートのコードで、空欄 ［ A ］ に入るものを選びなさい。

for ( i を 1 から n - 1 まで 1 ずつ増やす )
    for ( j を 1 から ［ A ］ まで 1 ずつ増やす )
        if ( a[j] が a[j + 1] より大きい )
            // 交換処理
        endif
    endfor
endfor
解説を表示 正解：イ
パスが進むごとに末尾が確定していきます。i=1のとき最後まで、i=2のとき末尾1個を除いて…と比較範囲が狭まるため n - i が正解です。
n - 1 にすると確定済み要素も毎回比較してしまい非効率です（動作は正しいですが）。

問題13-4　空欄補充

次の選択ソートのコードで、空欄 ［ B ］ に入るものを選びなさい。

for ( i を 1 から n - 1 まで 1 ずつ増やす )
    min_idx ← i
    for ( j を i + 1 から n まで 1 ずつ増やす )
        if ( a[j] が a[min_idx] より小さい )
            ［ B ］
        endif
    endfor
    // i と min_idx を交換
endfor
解説を表示 正解：ウ
より小さい要素が見つかったとき、その位置（インデックス）を min_idx に記録します。 値を直接代入するのではなく「どこに最小値があるか」を覚えておくのが選択ソートの特徴です。

問題13-5

次のコードはバブルソートと選択ソートのどちらか。またソート後の配列はどれか。

整数型の配列: a ← {3, 1, 4, 2}
整数型: i, j, tmp
整数型: n ← 4

for ( i を 1 から n - 1 まで 1 ずつ増やす )
    for ( j を 1 から n - i まで 1 ずつ増やす )
        if ( a[j] が a[j + 1] より大きい )
            tmp      ← a[j]
            a[j]     ← a[j + 1]
            a[j + 1] ← tmp
        endif
    endfor
endfor
解説を表示 正解：エ
a[j] と a[j+1] を比較して隣接交換しているのでバブルソートです。
{3,1,4,2} を昇順に並び替えると {1,2,3,4} になります。