問題
問98 4個の要素から成るデータの並びを，次の手順を繰り返して昇順に整列するとき，整列が終了するまでに(1)から(3)の一連の手順は，何回実行されるか。ここで，最初はデータの並び全体を整列対象とする。 データの並び：[27，42，33，12] 〔手順〕 (1) 整列対象中の要素の最大の値を選び，最後の要素と入れ替える。 (2) 最後の要素を整列対象から外す。 (3) 整列対象に要素が1個以上残っていれば，(1)から(3)の一連の手順を実行する。残っていなければ，整列完了なので終了する。
選択肢
- ア2
- イ3
- ウ4
- エ5
解説
正解：ウ
概要
この問題は、配列を昇順に並べ替えるアルゴリズムの処理回数を問うものです。提示されている手順は、最大値を選んで末尾と入れ替える「選択ソート」の考え方に基づいています。
正解の理由
データ数が4個の場合、最大値を選んで末尾に移動する操作を繰り返し、整列対象の範囲を1つずつ減らしていきます。整列対象が1個になるまで繰り返すため、実行回数は4−1＝3回です。したがって正しい回数は3回になります。
各選択肢の解説
ア（×）: 手順は整列対象の要素数が1個になるまで繰り返します。データが4個の場合は3回の処理が必要であり、2回では整列が完了しないため誤りです。
イ（〇）: データ数が4個の場合、最大値を選んで末尾と入れ替える処理を3回繰り返すことで整列が完了します。整列対象が1個になった時点で終了するため、この回数が正しいです。
ウ（×）: 4回実行すると、整列が完了した後にも余分な処理を行うことになります。選択ソートではn個のデータに対してn−1回の処理でよいため誤りです。
エ（×）: 5回はデータ数より多く、必要以上の処理回数です。問題の手順では整列対象が1個になるまで実行するため、この回数にはなりません。
ポイント
選択ソートでは、データ数がn個のとき最大値（または最小値）を選ぶ処理はn−1回行われます。