【科目B対策】最大値の位置を使って配列の要素を入れ替えるアルゴリズム
― 選択ソートの核心 ―
これまでに学んだことを整理します。
- 配列を順に見て最大値を求める
- 最大値の 位置（添字） を求める
ここまでできると、次に必ず出てくるのが
最大値を、正しい位置に移動させる
という処理です。
これは 選択ソート（Selection Sort） の最重要部分であり、
科目Bで非常に出題されやすいアルゴリズムです。
- 1. まずは配列の例
- 2. なぜ「末尾」と入れ替えるのか？
- 3. 単発：最大値と末尾を入れ替える擬似コード
- 4. 科目Bで超重要：なぜ TEMP が必要か？
- 5. 選択ソートとして拡張する
- 6. 処理のイメージ
- 6.1. 初期状態
- 6.2. 1回目の処理（last = 5）
- 6.3. 2回目の処理（last = 4）
- 6.4. 3回目の処理（last = 3）
- 6.5. 4回目の処理（last = 2）
- 6.6. 最終結果
- 6.7. ポイント①：last の意味を理解する
- 6.8. ポイント②：毎回やっている処理は同じ
- 6.9. ポイント③：試験では「動き」を問われる
- 6.10. まとめ
- 6.11. ① 絶対にやってはいけないメモ
- 6.12. ② 有効なメモの基本方針（重要）
- 6.13. ③ 選択ソート問題のメモサンプル
- 6.14. ④ 1回目の処理（last = 5）
- 6.15. ⑤ 2回目の処理（last = 4）
- 6.16. ⑥ 3回目の処理（last = 3）
- 6.17. ⑦ 4回目の処理（last = 2）
- 6.18. ⑧ 最終メモ（これが答え）
- 6.19. ⑨ メモのポイントまとめ（超重要）
- 6.20. ⑩ 試験でよくある失敗と回避策
- 6.21. ⑪ まとめ
- 7. 科目Bで狙われやすいポイント
- 8. まとめ（ここは必ず押さえる）
まずは配列の例
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風 擬似コード（最大値版）
A ← [ 7, 3, 9, 4, 6 ]
N ← LENGTH(A)
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
for i ← 1 to N
print A[i]
endfor処理のイメージ
1回目
→ 最大値を A[N] に確定
2回目
→ 残り（A[1]〜A[N-1]）から最大値を探す
3回目
→ さらに範囲を狭める
このように、確定領域が右から増えていくのが特徴です。
この処理は、次のことを 繰り返し 行っています。
- 配列の中から 最大値を探す
- 見つけた最大値を 右端（last番目）に移動
- 右端を「確定」として、探索範囲を狭める
これを 右から順に 確定させていくのが選択ソート（最大値版）の考え方です。
初期状態
A ← [ 7, 3, 9, 4, 6 ]
N ← 5| 添字 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 値 | 7 | 3 | 9 | 4 | 6 |
※ 基本情報試験では、配列の添字が 1 から始まる指定がよくあります。
1回目の処理（last = 5）
最大値を探す
初期状態：
MAX = 7
MAX_POS = 1| i | A[i] | MAX | 判定 |
|---|---|---|---|
| 2 | 3 | 7 | 更新なし |
| 3 | 9 | 7 | MAX=9, POS=3 |
| 4 | 4 | 9 | 更新なし |
| 5 | 6 | 9 | 更新なし |
👉 最大値は 9（位置3）
最大値を右端と交換
A[5] と A[3] を交換[ 7, 3, 6, 4, 9 ]👉 9 が確定（もう動かない）
2回目の処理（last = 4）
探索範囲は 1～4番目
最大値探索の結果：
- 最大値：7（位置1）
交換後：
[ 4, 3, 6, 7, 9 ]👉 7 と 9 が確定
3回目の処理（last = 3）
探索範囲は 1～3番目
- 最大値：6（位置3）
- 同じ位置なので交換後も変化なし
[ 4, 3, 6, 7, 9 ]4回目の処理（last = 2）
探索範囲は 1～2番目
- 最大値：4（位置1）
交換後：
[ 3, 4, 6, 7, 9 ]最終結果
3
4
6
7
9配列は昇順に並び替えられました。
ポイント①：last の意味を理解する
- last は 「まだ並び替えていない範囲の右端」
- last が小さくなるほど、右側は確定していく
ポイント②：毎回やっている処理は同じ
- 最大値を A[1] に仮定
- 範囲内で最大値を探す
- last 番目と交換
👉 回数が変わるだけで、処理内容は変わらない
ポイント③：試験では「動き」を問われる
基本情報技術者試験（科目B）では、
- 「何回目のループ後の配列」
- 「この時点で確定している要素」
- 「交換後の配列の状態」
といった トレース力 が問われます。
コードを丸暗記するよりも、
紙に書いて追えるか を意識しましょう。
まとめ
- 選択ソート（最大値版）は「右から確定」
- last が示す範囲を意識すると理解しやすい
- トレースできれば試験問題は解ける
基本情報技術者試験（CBT）では、
白紙のメモ用紙とペンが渡されます。
このメモは
👉 「計算を書く紙」ではなく「考えるための補助脳」
として使うのが正解です。
① 絶対にやってはいけないメモ
❌ コードを全文書き写す
❌ きれいに書こうとする
❌ 日本語の説明文を書く
→ 時間を失うだけで得点につながりません
② 有効なメモの基本方針（重要）
メモに書くのは、次の3つだけです。
- 配列の状態
- 今見ている範囲
- 確定した要素
③ 選択ソート問題のメモサンプル
問題例（頭の中）
A = [ 7, 3, 9, 4, 6 ]メモ用紙に最初に書くもの
[7][3][9][4][6]
1 2 3 4 5※ 添字は 必ず書く（試験では超重要）
④ 1回目の処理（last = 5）
メモの書き方
[7][3][9][4][6] | ← 5- | より右は 確定
- 今はまだ確定なし
最大値を探す → 9（3番）
交換後：
[7][3][6][4] | [9]👉 9 確定
⑤ 2回目の処理（last = 4）
[7][3][6][4] | [9]最大値 → 7（1番）
交換後：
[4][3][6] | [7][9]👉 7, 9 確定
⑥ 3回目の処理（last = 3）
[4][3][6] | [7][9]最大値 → 6（3番）
交換（変化なし）：
[4][3] | [6][7][9]⑦ 4回目の処理（last = 2）
[4][3] | [6][7][9]最大値 → 4（1番）
交換後：
[3][4][6][7][9]⑧ 最終メモ（これが答え）
[3][4][6][7][9]⑨ メモのポイントまとめ（超重要）
ポイント①
1行で書き直すのが正解
- × 何行も残す
- ○ 常に「今の状態」だけ残す
ポイント②
縦線「|」は最強の記号
- 左：未処理
- 右：確定
👉 言葉より速い
ポイント③
if 文や for 文は一切書かない
- コードは画面にある
- メモは「変化」だけを書く
⑩ 試験でよくある失敗と回避策
| 失敗 | 回避 |
|---|---|
| 添字を忘れる | 最初に必ず書く |
| 範囲を間違える | ` |
| 途中で混乱 | 1行だけ残す |
⑪ まとめ
- 科目Bは「暗記試験」ではない
- メモを使えるかどうかで難易度が変わる
- 正しいメモは、思考を助けてくれる
科目Bで狙われやすいポイント
① 内側ループの範囲
for i ← 2 to lastここを N まで回すと 論理破綻します。
② MAX と MAX_POS の初期化位置
for last ← ...
MAX ← A[1]
MAX_POS ← 1👉 外側ループの中で初期化するのが正解。
③ 入れ替えをしないケース
- すでに最大値が末尾にある→ それでも入れ替え処理は実行される
試験では
「無駄な処理があっても正しいか？」
を問われることがあります。
まとめ（ここは必ず押さえる）
- 最大値の「位置」が分かると入れ替えができる
- 入れ替えには TEMP を使う
- この構造がそのまま選択ソートになる
- 科目Bでは 範囲・初期化・代入順 が問われる
【問題1】
次の擬似言語は，配列 A の要素を昇順に並べ替える処理である。
A ← [ 7, 3, 9, 4, 6 ]
N ← LENGTH(A)
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外側の for ループが 1回目（last = 5） の処理を終了した直後の
配列 A の内容として，最も適切なものはどれか。
ア [ 7, 3, 6, 4, 9 ]
イ [ 6, 3, 7, 4, 9 ]
ウ [ 3, 4, 6, 7, 9 ]
エ [ 7, 3, 9, 4, 6 ]
正解
ア
解説
- 外側ループ 1 回目ではA[1] ～ A[5] の中から最大値を探す
- 配列 [ 7, 3, 9, 4, 6 ] の最大値は 9
- 最大値 9 を 末尾 A[5] に移動
- したがって，配列は[ 7, 3, 6, 4, 9 ]
👉 この時点で「9」は確定
👉 それ以外の順序はまだ整っていない
【問題2】
問題1と同じ擬似言語において，
外側の for ループが 2回目（last = 4） の処理を終了した直後の
配列 A の内容として，最も適切なものはどれか。
ア [ 4, 3, 6, 7, 9 ]
イ [ 6, 3, 4, 7, 9 ]
ウ [ 7, 3, 4, 6, 9 ]
エ [ 3, 6, 4, 7, 9 ]
正解：ア
解説
- 1回目終了時点[ 7, 3, 6, 4, 9 ]
- 2回目は A[1] ～ A[4] の中で最大値を探す
- 最大値は 7
- 7 を A[4] に移動
結果
[ 4, 3, 6, 7, 9 ]👉 後ろから順に「最大値が確定」していく
👉 これがこの処理の最大の特徴
【問題3】
次の擬似言語中の □ に入れるものとして，最も適切なものはどれか。
for i ← 2 to last
if A[i] > MAX then
MAX ← A[i]
□ ← i
endif
endforア MAX
イ TEMP
ウ MAX_POS
エ last
正解
ウ
解説
- MAX には 最大値そのもの を入れている
- 交換処理には「どこにあったか（添字）」 が必要
- そのため，位置を記録する変数MAX_POS ← i が正しい
👉 値と位置を混同させるのが典型的なひっかけ
【問題4】
配列の要素数を N とする。
問題1の擬似言語において，
外側の for ループが 1回実行される間に行われる
大小比較（A[i] > MAX）の回数として，最も適切なものはどれか。
ア N 回
イ N − 1 回
ウ N − 2 回
エ N² 回
正解
イ
解説
- 内側ループはi ← 2 to last
- last = N のとき比較回数は2 ～ N → N − 1 回
👉 回数問題は
👉 範囲を図に描けるかどうか が勝負
【問題5】
この処理についての記述として，正しいものはどれか。
ア 配列全体が常に昇順に並んでいることを前提としている
イ 各外側ループの終了時に，最大値が先頭に確定する
ウ 各外側ループの終了時に，最大値が末尾に確定する
エ 常に隣接する要素同士を比較している
正解
ウ
解説
- 各外側ループの目的は探索範囲の最大値を末尾に移動すること
- 隣同士の比較ではない → バブルソートではない
- 昇順が途中で完成するわけではない
👉 「末尾に確定」＝このコードの核
まとめ（試験で勝つために）
- 名前は覚えなくていい
- 見るべきは常にこの3点
- 今回の探索範囲
- 何が確定したか
- 値と位置の役割分担