基本情報 科目B ソート（整列）のトレース練習
基本情報技術者試験の科目Bで、探索（線形探索・二分探索）と並んで必ず出会うのが ソート（整列） です。配列を小さい順（昇順）や大きい順（降順）に並べ替える処理で、出題頻度が高い一方、外側と内側の 2 つのループ（二重ループ） が登場するため「i と j のどちらが今どこを指しているのか分からなくなる」と一気につまずきます。本記事は、代表的な 選択ソート を変数の値を表に書きながら 1 行ずつ追う トレース で攻略する練習帳です。合計・最大値・線形探索のトレース練習・二分探索のトレース練習 の続編にあたります。
本記事は 過去問AI が学習用に作成したオリジナルの例題です。掲載している擬似言語は IPA の過去問・公式サンプルの転載ではなく、説明用に書き起こしたものです。擬似言語の正式な記述形式は必ず IPA 公式ページ で確認してください。記法そのものの読み方は 基本情報 科目Bの擬似言語 記法早見表 にまとめています。
選択ソートは「最小値を見つけて前へ運ぶ」整列
選択ソートは、まだ並んでいない範囲から最小値を探し、その範囲の先頭と交換する ことを繰り返す整列です。1 周ごとに「確定した先頭」が 1 つずつ増えていきます。たとえば 5 個の配列なら、1 周目で全体の最小値が先頭（1 番目）に確定し、2 周目で残り 4 個の最小値が 2 番目に確定し……と進み、4 周で並べ替えが完了します（最後の 1 個は自動的に確定するので、外側ループは要素数 − 1 回）。
この記事の例題は、すべて次の約束ごとで進めます（科目Bの標準的なルールです）。
- 代入は ←（右の値を左の変数に入れる）。条件式の中の ＝ は「等しいか？」の比較
- 配列の 要素番号は 1 から始まる。A[1] が先頭、A[要素数] が末尾
- min は「最小値そのもの」ではなく「最小値がある位置（添字）」 を覚える変数。実際の値は A[min] で取り出す
記法そのものが不安なら、先に 記法早見表 で ← の扱いを確認してから戻ってくるとスムーズです。
例題のコード
昇順に並べ替えたい配列 A = {5, 2, 8, 1, 9}（要素数 5）を、選択ソートで小さい順に整列するコードです。
整数型: i, j, min, tmp
for (i を 1 から 4 まで 1 ずつ増やす)
min ← i
for (j を i + 1 から 5 まで 1 ずつ増やす)
if (A[j] < A[min])
min ← j
endif
endfor
if (min ≠ i)
tmp ← A[i]
A[i] ← A[min]
A[min] ← tmp
endif
endfor
読み方はこうです。外側の i は「これから確定させる位置」。まず min ← i として「今のところ i 番目が最小」と仮置きします。内側の j は i の 1 つ右から末尾までを順に見て、A[j] が今の最小値 A[min] より小さければ min を j に更新します。内側ループが終わると min には「i 番目以降で最も小さい値の位置」が入っているので、min が i と違う（＝もっと小さい値が後ろにあった）ときだけ A[i] と A[min] を 交換 します。
内側ループの動き（i = 1 のとき）
まず外側 i = 1 の周回で、内側ループがどう最小値の位置を見つけるかを追います。min は i = 1（A[1] = 5）から始まります。
| j | A[j] | 現在の最小 A[min] | A[j] < A[min]? | 更新後 min |
|---|---|---|---|---|
| 開始前 | − | A[1] = 5 | − | 1 |
| j = 2 | 2 | 5 | はい | 2 |
| j = 3 | 8 | 2 | いいえ | 2 |
| j = 4 | 1 | 2 | はい | 4 |
| j = 5 | 9 | 1 | いいえ | 4 |
内側ループが終わった時点で min = 4。つまり「1 番目以降で最も小さい値は 4 番目の A[4] = 1」と分かりました。min（4）≠ i（1）なので、A[1] と A[4] を tmp を使って交換します。配列は {1, 2, 8, 5, 9} になり、先頭の 1 が確定 しました。
外側ループ全体のトレース
同じ要領で外側 i = 1 〜 4 を回したときの、各周の結果だけをまとめます。「走査範囲 j」は内側ループが見る範囲、「min」は見つけた最小値の位置です。
| i（確定する位置） | 走査範囲 j | 見つけた min | 交換 | 交換後の配列 |
|---|---|---|---|---|
| 開始前 | − | − | − | 5, 2, 8, 1, 9 |
| i = 1 | 2〜5 | 4（値 1） | A[1] ↔ A[4] | 1, 2, 8, 5, 9 |
| i = 2 | 3〜5 | 2（値 2） | なし（min = i） | 1, 2, 8, 5, 9 |
| i = 3 | 4〜5 | 4（値 5） | A[3] ↔ A[4] | 1, 2, 5, 8, 9 |
| i = 4 | 5〜5 | 4（値 8） | なし（min = i） | 1, 2, 5, 8, 9 |
4 周終わって配列は {1, 2, 5, 8, 9} に整列しました。注目したいのは i = 2 と i = 4 では交換が起きていない 点です。すでに最小値がその位置にあるとき（min = i）は交換しません。ここで毎回必ず交換すると書いてしまうと、同じ値どうしを入れ替える無駄が出るだけでなく、設問によっては「交換回数」を問われたときに答えがずれます。
もう一つの定番：バブルソート
選択ソートと並んで頻出なのが バブルソート（隣接交換法） です。こちらは「隣り合う 2 つを比べ、左が大きければ交換する」を端から端まで繰り返し、大きい値を泡のように後ろへ押し上げます。選択ソートが「1 周で 1 回だけ交換（最小値を前へ）」なのに対し、バブルソートは「1 周で何度も隣どうしを交換する」のが違いです。トレースのコツは同じで、二重ループの i・j を表の列に固定し、交換のたびに配列の状態を 1 行書く こと。まずは交換が 1 周 1 回で追いやすい選択ソートで二重ループの感覚をつかむのがおすすめです。
つまずきやすい3つのポイント
- min は「値」ではなく「位置（添字）」。min に A[i] のような値を入れてしまうと、後で A[min] と書いたときに添字として使えず破綻します。比較は A[j] < A[min]、交換は A[min] と、つねに「位置を介して値を取り出す」と意識します。
- 交換は tmp を使う 3 行。A[i] ← A[min] を先に実行すると A[i] の元の値が消え、続く A[min] ← A[i] では両方が同じ値になって壊れます。必ず tmp ← A[i] で退避してから入れ替えます。
- 内側ループは i + 1 から始める。i 番目自身は「仮の最小」として基準にしているので、比べる相手は i の 1 つ右からです。j を i から始めると自分自身と比較する無駄が出ます（壊れはしませんが意図がぶれます）。
トレースで詰まらないためのコツ
二重ループは、表の 列を i・j・min・配列の状態 と決めてしまう のが最大のコツです。外側 i が 1 つ進むたびに区切り線を引き、その中で内側 j を 1 行ずつ動かすと、「今は何番目を確定させる周回で、内側はどこまで見たか」が一目で分かり、迷子になりません。配列の状態は交換が起きた行にだけ書き換えれば十分です。
次のステップ
ソートが追えるようになったら、出題範囲のアルゴリズムを一通りトレースで体験するのが近道です。基礎の 合計・最大値・線形探索のトレース練習、半分ずつ絞り込む 二分探索のトレース練習 をまだ見ていなければ先にそちらを、最難関の 再帰のトレース練習 ではコールスタックの上り下りを階乗で 1 段ずつ追えます。読む速度を上げる訓練法は 基本情報科目B｜擬似言語アルゴリズム読解の3ステップ訓練法 で扱っています。つまずきが記法なのかトレースなのか切り分けたいときは 科目Bがわからない人へ、科目B 全体の進め方は 基本情報技術者 科目B完全対策 が地図になります。
手を動かす練習台としては、過去問AI の 基本情報 アルゴリズムとプログラミング分野の過去問 が使えます（こちらは科目A 相当の選択式で、科目B そのものの形式ではない点だけ意識してください）。各問題ページの AI コパイロットに「この選択ソートのコードを i・j・min を列にした表で 1 行ずつトレースして」と頼めば、本記事と同じ追い方を対話でその場で再現できます。
よくある質問
Q. 選択ソートの min には最小値そのものを入れるのですか？ いいえ。min に入れるのは「最小値がある位置（添字）」です。値そのものではありません。最小値の実際の数は A[min] と書いて取り出します。位置で覚えておくと、最後に A[i] と A[min] を交換するときにそのまま添字として使えます。min に値を入れてしまうと A[min] が添字として成立せず破綻するので、「min は場所、A[min] が中身」と区別してください。
Q. なぜ交換に tmp という変数を使うのですか？ 2 つの箱の中身を入れ替えるには、一方を一時的に避けておく場所が必要だからです。tmp を使わず A[i] ← A[min] を先に実行すると、A[i] の元の値が上書きされて消え、続く A[min] ← A[i] では両方が同じ値になってしまいます。必ず tmp ← A[i] で退避し、A[i] ← A[min]、最後に A[min] ← tmp の 3 行で入れ替えます。
Q. 内側ループはなぜ i ではなく i + 1 から始めるのですか？ i 番目はその周回で「仮の最小値」として基準にしているため、比べる相手は i の 1 つ右からで十分だからです。j を i から始めると A[i] と A[i] を比較する無駄な 1 回が入ります。壊れはしませんが、IPA の設問では開始位置が i + 1 になっていることが多いので、コードの for の範囲をそのまま読み取る習慣をつけてください。
Q. 選択ソートとバブルソートはどちらが出ますか？ どちらも科目Bで頻出で、過去のサンプル問題でも整列は定番テーマです。選択ソートは「最小値を見つけて 1 周に 1 回だけ交換」、バブルソートは「隣どうしを比べて何度も交換」と動きが違うため、両方の動きを 1 度ずつトレースしておくと安心です。まずは交換回数が少なく追いやすい選択ソートで二重ループの読み方に慣れるのがおすすめです。
まとめ
- 選択ソートは 未整列の範囲から最小値を見つけ、その先頭と交換 する整列。外側ループは要素数 − 1 回
- min は 最小値の「位置（添字）」。値は A[min] で取り出す
- 交換は tmp を使う 3 行。tmp なしだと値が消えて壊れる
- 内側ループは i + 1 から 末尾まで。min = i のときは交換しない
- 二重ループは i・j・min・配列の状態を表の列に固定 し、外側が進むたびに区切って 1 行ずつ追う
線形探索 → 二分探索 → ソートとトレースで追えるようになれば、科目Bのアルゴリズム設問の主要パターンはひと通り読めるようになります。