【科目B対策】選択ソート（最小値版）への発展

2026年2月2日

前回の「最小値探索」は、配列の中から 最小値を1つ見つける だけでした。

これを発展させて、

• 1回目：全体の最小値を先頭に置く
• 2回目：残り（2番目以降）の最小値を2番目に置く
• 3回目：残り（3番目以降）の最小値を3番目に置く

…という処理を繰り返すと、配列全体が昇順に並びます。

これが 選択ソート（Selection Sort） です。

---

サンプルデータ

A ← [ 7, 3, 9, 4, 2 ]

---

考え方（超重要）

選択ソート（最小値版）は、次の繰り返しです。

1. 未整列部分（i ～ N）の中から 最小値の位置 minIndex を探す
2. A[i] と A[minIndex] を入れ替える
3. i を1つ進める

ポイントは

「最小値そのもの」ではなく「最小値の位置（添字）」を覚えることです。

（科目Bはここを問う出題が多いです）

---

擬似コード（選択ソート：最小値版）

基本情報の擬似言語の雰囲気に合わせて書きます。

A ← [ 7, 3, 9, 4, 2 ]
N ← LENGTH(A)

for i ← 1 to N - 1

  minIndex ← i

  for j ← i + 1 to N
    if A[j] < A[minIndex] then
      minIndex ← j
    endif
  endfor

  TEMP ← A[i]
  A[i] ← A[minIndex]
  A[minIndex] ← TEMP

endfor

print A[1]
print A[2]
print A[3]
print A[4]
print A[5]

---

1周ずつ、何が起きているか

1回目（i = 1）

未整列部分：[ 7, 3, 9, 4, 2 ]

最小値は 2（位置5）なので、A[1]とA[5]を交換。

[ 2, 3, 9, 4, 7 ]

2回目（i = 2）

未整列部分：[ 3, 9, 4, 7 ]

最小値は 3（位置2）なので交換なし。

[ 2, 3, 9, 4, 7 ]

3回目（i = 3）

未整列部分：[ 9, 4, 7 ]

最小値は 4（位置4）なので A[3] と A[4] を交換。

[ 2, 3, 4, 9, 7 ]

4回目（i = 4）

未整列部分：[ 9, 7 ]

最小値は 7（位置5）なので A[4] と A[5] を交換。

[ 2, 3, 4, 7, 9 ]

---

最小値探索との関係

• 最小値探索：配列の最小値を1つ見つける
• 選択ソート：最小値探索を「範囲を狭めながら」繰り返して並べ替える

つまり、選択ソートは

「最小値探索をN-1回やってるだけ」

と理解すると一気に楽になります。

---

科目Bで狙われるポイント

① minIndex の更新タイミング

minIndex ← j が入るのは、値が更新されたときだけ。

② 内側ループの開始が i+1 になる理由

すでに minIndex ← i で候補に入れているので、

i 自身と比較する必要がなく、次の要素から見ればよい。

③ swap（入れ替え）が必ず書かれているか

科目Bはここを抜いたり、入れ替え先を間違えた擬似コードを出してきます。

---

まとめ

• 選択ソート（最小値版）は「未整列部分の最小値を先頭へ」を繰り返す
• 最小値の位置 minIndex を覚えるのが肝
• 科目Bでは添字、範囲、swapミスを狙ってくる

---