問98 最大値を後ろへ送る整列

ITパスポート 令和7年度 公開問題、全100問のうちの問98。

出典:令和7年度 ITパスポート試験 公開問題 問98

4個の要素から成るデータの並びを,次の手順を繰り返して昇順に整列するとき,整列が終了するまでに(1)から(3)の一連の手順は,何回実行されるか。ここで,最初はデータの並び全体を整列対象とする。

データの並び:[2⁠7,4⁠2,3⁠3,1⁠2]

〔手順〕

(1) 整列対象中の要素の最大の値を選び,最後の要素と入れ替える。

(2) 最後の要素を整列対象から外す。

(3) 整列対象に要素が1個以上残っていれば,(1)から(3)の一連の手順を実行する。残っていなければ,整列完了なので終了する。

  1. ア2
  2. イ3
  3. ウ4
  4. エ5
答えと解説を開く

正解はウです。

この手順は、整列対象の中でいちばん大きい値を最後に送り、その最後を対象から外す、を繰り返します。[2⁠7,4⁠2,3⁠3,1⁠2] で順に追います。1 回目は、最大の 4⁠2 と最後の 1⁠2 を入れ替え、[2⁠7,1⁠2,3⁠3,4⁠2] になります。4⁠2 を外し、対象は [2⁠7,1⁠2,3⁠3] です。2 回目は、最大の 3⁠3 がすでに最後にあるので、入れ替えても変わりません。3⁠3 を外し、対象は [2⁠7,1⁠2] です。3 回目は、最大の 2⁠7 と最後の 1⁠2 を入れ替え、[1⁠2,2⁠7] になります。2⁠7 を外し、対象は [1⁠2] です。まだ要素が 1 個残っているので、4 回目を実行します。最大の 1⁠2 を最後 (自分自身) と入れ替え、1⁠2 を外すと対象は空になります。これで終了です。だから正解はウです。

ほかの選択肢が違う理由

  • ア2 回では、まだ [2⁠7,1⁠2] の 2 個が残っていて、並べ終わっていません。
  • イ3 回目のあとも、整列対象に 1⁠2 の 1 個が残っています。手順 (3) では「1 個以上残っていれば」続けるので、もう 1 回実行します。
  • エ要素は 4 個で、1 回の実行で 1 個ずつ外れます。4 回で整列対象が空になるので、5 回目は実行されません。

仕組み

この手順は選択ソートの一種です。1 回ごとに 1 個が正しい位置に決まり、対象から外れます。

回数の問は終わりの条件をよく読みます。この問は「1 個以上残っていれば続ける」なので、最後の 1 個にも手順を実行し、要素の数と同じ 4 回になります。

この問に出る言葉