選択ソートの実行回数を数える、残り1個のときの扱い
ITパスポート試験 令和7年度 問98 ／ アルゴリズムとプログラミング › アルゴリズムとプログラミング
過去問にチャレンジ
4個の要素から成るデータの並びを，次の手順を繰り返して昇順に整列するとき，整列が終了するまでに(1)から(3)の一連の手順は，何回実行されるか。ここで，最初はデータの並び全体を整列対象とする。 データの並び：[27, 42, 33, 12] 〔手順〕 (1) 整列対象中の要素の最大の値を選び，最後の要素と入れ替える。 (2) 最後の要素を整列対象から外す。 (3) 整列対象に要素が1個以上残っていれば，(1)から(3)の一連の手順を実行する。残っていなければ，整列完了なので終了する。
- ア
2
- イ
3
- ウ
4
- エ
5
会話形式の解説
講師この問題は、最大値を末尾に移して整列対象から外していく整列の手順が、何回くり返されるかを数える問題です。並べ替えの結果より、手順(3)の続ける条件がポイントになります。
受験者4個の並びを整列するなら、3回で済むと思いました。最後の1個は比べる相手がいないので、もう整列済みですよね。
講師そこがこの問題の引っかけどころです。頭の中で考えるより、実際にデータを動かしてみましょう。1回目は、対象全体の最大値42を末尾の12と入れ替えて[27, 12, 33, 42]にし、42を対象から外します。
受験者2回目は[27, 12, 33]が対象で、最大値の33はもう末尾にあります。この場合は入れ替えがないので、回数に数えないのでしょうか。
講師入れ替えが起きないだけで、手順としては1回実行しています。33を外して、2回目は終わりです。3回目は[27, 12]が対象で、最大値27を12と入れ替えて全体が[12, 27, 33, 42]になり、27を外します。
受験者この時点で並びはもう昇順です。私が3回と考えたのはここで終わると思ったからですが、まだ続くのですか。
講師手順(3)をよく読んでください。「整列対象に要素が1個以上残っていれば」続けるとあります。3回目の後も、対象には12が1個残っていますね。
受験者1個以上なので、1個でも残っていれば続けるのですね。では4回目は12だけが対象で、12を自分自身と入れ替えたことになり、外すと対象が0個になって終わり、ということでしょうか。
講師そのとおりです。なので正解は4回です。見た目が整列済みかどうかではなく、条件どおりに数えるのがコツです。2回とする選択肢は、2回目の後に27と12の2個がまだ残っているので誤りです。
受験者5回とする選択肢は、4回目で対象が0個になった後にもう1回数えてしまった場合ですね。残りがないと判定された時点で終わるので、5回目はありません。
講師よく整理できています。1回実行するごとに対象が1個ずつ減るので、4個から0個になるまでちょうど4回、つまり要素数がnならn回と考えられます。
講師補足です。もし条件が「2個以上残っていれば」なら、残り1個のときは実行しないのでn−1回になります。「以上」と「より多い」、「1個」と「2個」の違いで答えが変わるので、条件文は一字ずつ丁寧に読んでください。
まとめ
この問題の手順は、整列対象の最大値を末尾に置いて対象から外していく選択ソートの一種です。[27, 42, 33, 12]で実際に動かすと、1回ごとに対象が4→3→2→1→0個と減ります。続行条件が「1個以上残っていれば」なので、残り1個のときも実行され、実行回数は4回です。途中で並びが整列済みに見えたり、入れ替えが起きなかったりしても、手順を1回実行したことに変わりはありません。条件が「2個以上」ならn−1回になるため、条件文の細かな違いに注意が必要です。
解答・解説
正解はウです
この問題のテーマ
最大値を末尾へ移し、その要素を整列対象から外していく選択ソートについて、手順(1)〜(3)が何回実行されるかを数える問題です。
解き方の考え方
データの並びを実際に手で動かし、1回ごとに整列対象がどう変わるかを書き出します。手順を1回実行するたびに末尾の要素が1個外れるので、対象の要素数は4→3→2→1→0と減っていきます。大事なのは、手順(3)の続行条件が「1個以上残っていれば」だという点です。対象が1個だけになったときも、もう1回実行します。
・1回目：対象[27,42,33,12]の最大値42を末尾の12と入れ替えて[27,12,33,42]にし、42を外します。
・2回目：対象[27,12,33]の最大値33はすでに末尾にあるので並びは変わらず、33を外します。
・3回目：対象[27,12]の最大値27を12と入れ替えて[12,27,33,42]にし、27を外します。
・4回目：対象は12だけです。12を自分自身と入れ替えたことになり、12を外すと対象は0個になって終了します。
したがって実行回数は4回で、正解のウと一致します。
選択肢ごとの解説
- ×ア 22回とする考え方は誤りです。2回実行した時点では、整列対象に27と12の2個がまだ残っています。手順(3)の条件を満たすので、手順は続けて実行されます。
- ×イ 33回とする考え方は誤りです。3回目の後で並びは[12,27,33,42]となり、見た目は整列済みです。しかし整列対象には12が1個残っており、「1個以上残っていれば」続行する条件に当てはまります。要素数4から1を引いた回数と考え、残り1個のときの実行を見落とすと、この選択肢を選んでしまいます。
- ○ウ 44回とする考え方は正しいです。手順を1回実行するごとに要素が1個ずつ対象から外れるので、4個の対象が0個になるまでにちょうど4回かかります。4回目は12だけが対象で並びは変わりませんが、手順としては実行されています。
- ×エ 55回とする考え方は誤りです。4回目の実行で最後の12が外れ、対象は0個になります。手順(3)で残りがないと判定された時点で終了するので、5回目は行われません。
補足
続行条件が「2個以上残っていれば」であれば、残り1個のときは実行されないため、実行回数はn−1回になります。このような問題では、条件の「以上」と「より多い」、「1個」と「2個」の違いで答えが変わるので、条件文を丁寧に読むことが大切です。また、最大値がすでに末尾にある回（今回の2回目）も、入れ替えが起きないだけで1回として数えます。
POINT
- この手順は、最大値を末尾に置いて対象から外していく選択ソートの一種です。
- 一連の手順を1回実行するごとに、整列対象は1個ずつ減ります。
- 続行条件が「1個以上残っていれば」の場合、要素数がnなら実行回数はn回になります。
- 途中で並びが整列済みに見えても、手順は条件どおり最後まで実行されます。