ITパスポート 令和7年度 問98：algorithmに関する問題

答えは c「4」 です。

やることは「一番大きい数字を見つけて、列のいちばん後ろの席と入れ替える→その後ろの席は確定したので外す」を、残りがなくなるまでくり返すだけです。

[27,42,33,12] は4人います。

1回目：4人から最大を後ろへ→3人残る

2回目：3人から最大を後ろへ→2人残る

3回目：2人から最大を後ろへ→1人残る

4回目：1人だけ→そのまま確定して0人に→終了

くり返した回数は 4回 です。

👉 覚え方：要素が1個になっても"もう1回"回って終わる。だから人数とおなじ4回。

なぜこれが正解か

正解は c（4回）。これは選択ソート（最大値を末尾へ送る方式）の動作。手順(3)が「要素が1個以上残っていれば繰り返す」なので、整列対象が0個になるまで(1)〜(3)を回す。

[27,42,33,12]（4要素）でのトレース：

1. 4要素→最大42を末尾12と交換→[27,12,33,42]、42を外す（残3）

2. 3要素[27,12,33]→最大33を末尾と交換→[27,12,33]、外す（残2）

3. 2要素[27,12]→最大27を末尾と交換→[12,27]、外す（残1）

4. 1要素[12]→最大は自分自身、交換し外す（残0）→終了

よって実行回数は 4回。

ひっかけ注意

「n要素なら n−1 回」と覚えていると3回と誤答する。本問は手順(3)の判定が「1個以上残っていれば繰り返す」ため、残り1個でももう一巡するのがポイント。判定条件を丁寧に読むこと。

理論的背景

この問題で示されているアルゴリズムは「選択ソート（Selection Sort）」の変形で、各パスで最大値を末尾に移動させる降順選択ソートを昇順に利用している。計算量はO(n²)であり、n要素の場合に最大n-1回のパスが必要となる。ただし本問の「整列対象に要素が1個以上残っていれば繰り返す」という終了条件に注目する必要がある。要素数n=4の場合の具体的な実行フロー：第1回([27,42,33,12]→最大42を末尾と交換→[27,12,33,42])、第2回([27,12,33]→最大33を末尾と交換→[27,12,33])、第3回([27,12]→最大27を末尾と交換→[12,27])、第4回([12]→要素1個→入れ替え実施後に整列対象から外す→空になる)。手順(3)の「整列対象に要素が1個以上残っていれば(1)から実行」という条件は「1個でも実行する」ため、最後の1要素の状態でも(1)(2)を実行してから終了する。したがって4回実行される。

実務での使われ方

選択ソートは実装が単純明快なため、アルゴリズム教育の入門として広く採用されているが、本番システムでは使われることはほぼない。実業務ではクイックソート（O(n log n)平均）、マージソート（O(n log n)安定）、あるいはTimSort（Python・Javaの標準ライブラリ実装）が使われる。TimSortはマージソートと挿入ソートを組み合わせた実用的なアルゴリズムで、現実データ（部分的に整列済みのケースが多い）に対して高いパフォーマンスを発揮する。データベースのインデックス構造（B+木）やハードウェアソータなど特殊用途では全く異なるアルゴリズムが用いられるが、ITパスポート〜基本情報の範囲では「アルゴリズムのステップ数を手で数える能力」が問われる。

試験での位置づけ

アルゴリズムのトレースは基本情報技術者試験・科目Bの中核テーマだが、ITパスポートでも「何回ループするか」という計算問題として出題が増えている。本問は「手順を1回ずつ丁寧に追う」トレース能力の測定問題で、よくある誤答パターンは「要素が1個残った時点で終了」と判断してしまう3回（c以外の選択肢）を選ぶミスである。本問の解法ポイントは「終了条件を正確に読む」こと。「残っていなければ終了」は「1個残っていても実行する」を意味する。近年のシラバス改訂でプログラミング的思考・疑似コード読解が強化され、このタイプの問題は今後さらに増加傾向にある。

選択肢の発展補足

選択肢a「2回」はn-2回（要素を2個残した時点で止まると誤解した場合）。選択肢b「3回」はn-1回（要素1個残った時点で止まると誤解した場合）で最も多い誤答パターン。これはバブルソートの標準的な実行回数（n-1パス）と混同することによる。選択肢d「5回」はn+1回（存在しない6個目のループを実行するという誤解）。4要素のソートアルゴリズムの比較：バブルソート最悪6回の比較、挿入ソート最悪6回の比較、選択ソート常に6回の比較（ただし交換回数は最大3回）。選択ソートの特徴は「交換回数が常にn-1回以下」で、交換コストが高い場合（ディスクI/O等）には有利になるケースもある。