問題
問3
次の記述中の【 】に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1から始まる。
次の手続 sort は，大域の整数型の配列 data の，引数 first で与えられた要素番号から引数 last で与えられた要素番号までの要素を昇順に整列する。ここで，first ＜ last とする。手続 sort を sort(1, 5) として呼び出すと，/*** α ***/ の行を最初に実行したときの出力は “【 】” となる。
- 1 2 3 4 5
- 1 2 3 5 4
- 2 1 3 4 5
- 2 1 3 5 4
[出典：基本情報技術者試験 令和5年度(科目B) 問3]
スポンサーリンク
正解
正解は「エ」です。
解説
この問題は「クイックソート」のアルゴリズムを理解しているかどうかが問われています。
配列 data = {2, 1, 3, 5, 4} に対して sort(1, 5) を実行すると、再帰的に配列の一部を並び替えながら最終的に全体を昇順にソートする処理が行われます。ただし、出力されるのは最終的なソート結果ではなく、「*** α ***」の行（最初に出力処理が呼び出される箇所）の時点の内容です。
この手続の中で最初に呼ばれる出力処理は、最初の再帰分割が終わったあと、左側のサブ配列に対して sort(first, i-1) を実行する前の段階です。このタイミングで data の中身は以下の通りとなります。
まず、pivotの値をdata[(1+5)÷2] = data[3] = 3とし、i=1, j=5から探索が始まります。
- data[i] = 2 < 3 → i++
- data[i] = 1 < 3 → i++
- data[i] = 3 == 3 → ストップ（i=3）
- data[j] = 4 > 3 → j–
- data[j] = 5 > 3 → j–
- data[j] = 3 == 3 → ストップ（j=3）
i ≥ j なのでループ終了。その前に data[i] と data[j] を交換（i=jなので交換しても変化なし）
その後の配列状態は変わらず {2, 1, 3, 5, 4} であり、次の再帰呼び出しに進む前に出力が行われます。したがって「最初に実行される出力」の内容はこの時点での配列です。これを要素番号順に出力すると「2 1 3 5 4」となり、選択肢「エ」が正解です。
ア(1 2 3 4 5):
これは完全に整列された状態ですが、これは再帰処理がすべて終わったあとの最終結果です。最初の出力時点ではまだ整列途中なので不正解です。
イ(1 2 3 5 4):
この並びは中間段階の一つに似ていますが、最初の出力時点ではi,jの交換が1回も行われておらず、実際の状態と一致しません。
ウ(2 1 3 4 5):
これは初期状態から最後の2要素が入れ替わっただけの状態ですが、最初の出力の時点ではそのような変更はまだ起こっていません。
難易度
この問題は、クイックソートのアルゴリズムの理解と、実行の各ステップでの配列状態を正確に把握できるかが問われています。初学者にとっては再帰処理のタイミングやpivot選択による分割処理の影響を追うことが難しいため、「やや難しい」レベルの問題と言えます。
スポンサーリンク
用語補足
クイックソート：
基準値（pivot）を用いて、データを小さいグループと大きいグループに分け、それぞれを再帰的にソートしていく高速なソート手法です。
再帰：
関数や手続きが自分自身を呼び出す構造のことで、処理を分割して繰り返し実行するときに用います。例として、フォルダの中にフォルダがある構造を処理する時に使われます。
pivot（ピボット）：
クイックソートにおいて基準となる値のことで、これをもとに配列の値を2つのグループに分けてソートを進めます。
対策
ソートアルゴリズムのうち、特にクイックソートやマージソートなどの「分割と再帰」に基づく手法はよく出題されます。図を書きながら処理の流れを追う練習をすると効果的です。また、実際に紙に手続きを書いて配列の状態を追跡することで理解が深まります。
