この問題の解説と、これまでの解答の記録です。
4個の要素から成るデータの並びを, 次の手順を繰り返して昇順に整列するとき, 整列が終了するまでに(1)から(3)の一連の手順は, 何回実行されるか。ここで, 最初はデータの並び全体を整列対象とする。 データの並び : [27, 42, 33, 12] 〔手順〕 (1) 整列対象中の要素の最大の値を選び, 最後の要素と入れ替える。 (2) 最後の要素を整列対象から外す。 (3) 整列対象に要素が1個以上残っていれば, (1)から(3)の一連の手順を実行する。残っていなければ, 整列完了なので終了する。
2は実行回数を大幅に少なく見積もっている。要素は4個あり、毎回1個ずつ確定して外すため、最低でも要素を減らす回数が必要。2回では対象が2個残った状態で止まり整列が完了しないので誤り。
3は『要素数Nの整列はN−1回で済む』という一般的な選択ソートの感覚で数えた誤り。この手順では終了条件が『1個以上残っていれば繰り返す』であり、対象が1個残った状態でもさらに(1)〜(3)を1回実行してから0個になる。そのため3回ではなく4回となる。
正解 手順は選択ソートで、毎回『整列対象の最大値を末尾と入れ替え、その末尾を対象から外す』ことを繰り返す。対象を実際に追跡すると、対象の要素数は 4→3→2→1→0 と1個ずつ減る。手順(3)の終了条件は『要素が1個以上残っていれば繰り返す』なので、対象が4個・3個・2個・1個のときにそれぞれ(1)〜(3)を1回ずつ実行し、対象が0個になった時点で終了する。すなわち実行回数は最初の4個から数えて4回。よって正解はウ(4)。
5は1回多く数えている。対象が0個になった時点で手順(3)の条件を満たさず終了するため、0個に対して(1)〜(3)を実行することはない。実行されるのは対象が4・3・2・1個の計4回までで、5回目は発生しないので誤り。