【科目B対策】最大値の位置を使って配列の要素を入れ替えるアルゴリズム
― 選択ソートの核心 ―
これまでに学んだことを整理します。
- 配列を順に見て最大値を求める
- 最大値の 位置（添字） を求める
ここまでできると、次に必ず出てくるのが
最大値を、正しい位置に移動させる
という処理です。
これは 選択ソート（Selection Sort） の最重要部分であり、
科目Bで非常に出題されやすいアルゴリズムです。
目次
まずは配列の例
A ← [ 7, 3, 9, 4, 6 ]
N ← LENGTH(A)今回は、
- 最大値を探す
- 見つかった最大値を 末尾と入れ替える
という処理を行います。
なぜ「末尾」と入れ替えるのか？
配列を並び替えるとき、
- 最大値 → 一番右
- 最小値 → 一番左
に置いていくと、
確定した部分が増えていくためです。
選択ソートでは、
「未整列の範囲」から最大値を探し、末尾に確定させる
という操作を繰り返します。
単発：最大値と末尾を入れ替える擬似コード
まずは 1回分の処理 を見ます。
最大値の位置を求める
MAX ← A[1]
MAX_POS ← 1
for i ← 2 to N
if A[i] > MAX then
MAX ← A[i]
MAX_POS ← i
endif
endfor最大値と末尾を入れ替える
TEMP ← A[N]
A[N] ← A[MAX_POS]
A[MAX_POS] ← TEMPこれで、
[ 7, 3, 9, 4, 6 ]は、
[ 7, 3, 6, 4, 9 ]になります。
最大値 9 が末尾に確定しました。
科目Bで超重要：なぜ TEMP が必要か？
次のように書きたくなりがちですが、
A[N] ← A[MAX_POS]
A[MAX_POS] ← A[N]これは 誤りです。
1行目で A[N] の元の値が失われるためです。
正しい考え方
- 一時的に退避させる変数（TEMP）を使う
- 3ステップで交換する
TEMP ← A[N]
A[N] ← A[MAX_POS]
A[MAX_POS] ← TEMP👉 この形は 科目B頻出テンプレート です。
選択ソートとして拡張する
ここまでの処理を「繰り返す」と、選択ソートになります。
科目B風 擬似コード（最大値版）
for last ← N downto 2
MAX ← A[1]
MAX_POS ← 1
for i ← 2 to last
if A[i] > MAX then
MAX ← A[i]
MAX_POS ← i
endif
endfor
TEMP ← A[last]
A[last] ← A[MAX_POS]
A[MAX_POS] ← TEMP
endfor処理のイメージ
1回目
→ 最大値を A[N] に確定
2回目
→ 残り（A[1]〜A[N-1]）から最大値を探す
3回目
→ さらに範囲を狭める
このように、確定領域が右から増えていくのが特徴です。
科目Bで狙われやすいポイント
① 内側ループの範囲
for i ← 2 to lastここを N まで回すと 論理破綻します。
② MAX と MAX_POS の初期化位置
for last ← ...
MAX ← A[1]
MAX_POS ← 1👉 外側ループの中で初期化するのが正解。
③ 入れ替えをしないケース
- すでに最大値が末尾にある→ それでも入れ替え処理は実行される
試験では
「無駄な処理があっても正しいか？」
を問われることがあります。
まとめ（ここは必ず押さえる）
- 最大値の「位置」が分かると入れ替えができる
- 入れ替えには TEMP を使う
- この構造がそのまま選択ソートになる
- 科目Bでは 範囲・初期化・代入順 が問われる
訪問数 4 回, 今日の訪問数 4回