令和7年度 ITパスポート試験 公開問題 問98 解説 整列アルゴリズム

この問題のポイントは、手順(3)に書かれた「整列対象に要素が1個以上残っていれば、(1)から(3)の手順を実行する」という終了条件を正確に追うことです。一般的な並べ替え（ソート）のアルゴリズムでは、最後の1個は自動的に場所が決まるため $n-1$ 回の処理で終わることも多いですが、この問題のルールでは要素がなくなるまで繰り返すため、4個の要素に対して4回の手順が実行されます。

手順を1回実行するごとに整列対象の要素が1つずつ減っていく様子を追いかけると、実行回数が導き出せます。

1回目： 整列対象は [27, 42, 33, 12] の4個です。 (1) 最大値 42 を選び、最後の要素 12 と入れ替えます。データの並びは [27, 12, 33, 42] となります。 (2) 42 を対象から外し、整列対象は [27, 12, 33] の3個になります。 (3) 3個残っているため、2回目を実行します。

2回目： 整列対象は [27, 12, 33] です。 (1) 最大値 33 を選び、最後の要素 33 と入れ替えます（位置は変わりません）。 (2) 33 を対象から外し、整列対象は [27, 12] の2個になります。 (3) 2個残っているため、3回目を実行します。

3回目： 整列対象は [27, 12] です。 (1) 最大値 27 を選び、最後の要素 12 と入れ替えます。データの並びは [12, 27, 33, 42] となります。 (2) 27 を対象から外し、整列対象は [12] の1個になります。 (3) 1個残っているため、4回目を実行します。

4回目： 整列対象は [12] です。 (1) 最大値 12 を選び、最後の要素 12 と入れ替えます。 (2) 12 を対象から外し、整列対象は 0個になります。 (3) 要素が残っていないため、整列完了となり終了します。

以上の通り、手順(3)の条件により合計4回の手順が実行されることになります。

flowchart TD
    START[開始: 整列対象 4個] --> R1[1回目実行]
    R1 --> C1{3個残っている?}
    C1 -- Yes --> R2[2回目実行]
    R2 --> C2{2個残っている?}
    C2 -- Yes --> R3[3回目実行]
    R3 --> C3{1個残っている?}
    C3 -- Yes --> R4[4回目実行]
    R4 --> C4{0個残っている?}
    C4 -- No --> END[整列終了]

この問題で使われている手法は、選択ソート（セレクションソート）と呼ばれるアルゴリズムの一種です。選択ソートは、未整列のデータの中から最大値（または最小値）を探し出し、それを端の要素と交換することを繰り返して並べ替えます。

ITパスポート試験において、ソートアルゴリズムは頻出のテーマです。選択ソートのほかにも、隣り合う要素を比較して交換する「基本交換法（バブルソート）」や、整列済みの列に適切な値を挿入していく「基本挿入法（インサーションソート）」などがよく出題されます。

アルゴリズムの実行回数や計算量を考える際、一般的には要素数を $n$ とすると、およそ $n^2$ に比例する時間がかかる（$O(n^2)$）という特徴があります。今回の問題のように、具体的な手順が示されている場合は、その手順を忠実にトレース（追跡）することが、ケアレスミスを防ぎ正解にたどり着くための確実な方法です。特に、繰り返しを終了するタイミングが「要素が残り1個になったとき」なのか「0個になったとき」なのかという、条件式のわずかな違いで答えが変わるため、手順(3)のような終了条件の記述を注意深く読む習慣をつけましょう。

選択ソート - Wikipedia https://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88

選択ソート（Selection Sort）とは - IT用語辞典 e-Words https://e-words.jp/w/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88.html

【1分解法】基本情報技術者試験 選択ソート https://www.youtube.com/watch?v=R9K2S8BwYg4