[平成２７年度春] 午後 問8解説

[問題文・解答]

平成２７年度４月に実施された基本情報技術者試験の午後試験の問題・解答はIPA公式ページからダウンロード出来ます。（以下リンク）

[H27春 午後 問題文]　　　[H27春 午後 解答]

[問題概要]

この問題は必須問題です。
出題分野はデータ構造及びアルゴリズムで、問題の題材はクイックソートを応用した選択アルゴリズムです。
クイックソートの動作をしっかりトレース出来る必要があり、かなり複雑な問題です。

[設問1]

クイックソートは、データの並べ替えアルゴリズムである基準値（ピボット）より大きいグループと小さいグループに分けて、それぞれのグループで新たに基準値を選んで２つのグループに分割するという処理を繰り返して整列します。

a) 設問1の例での(1)選択処理１回目の詳細な動作は以下のようになります。
①引数よりn=7, k=3, x=[3,5,6,4,7,2,1]
②3-4行目：Top=1, Last=7
③5行目：Top < Lastなのでループに入る
④6-8行目：Pivot=6, i=1, j=7
⑤10-15行目：x[i]がPivot以上、x[j]がPivot以下となるまで更新される。i=3, j=7
⑥16-18行目：i<jなのでループ続行
⑦19-23行目：x=[3,5,1,4,7,2,6], i=4, j=6
⑧10-15行目：x[i]がPivot以上、x[j]がPivot以下となるまで更新される。i=5, j=6
⑨16-18行目：i<jなのでループ続行
⑩19-23行目：x=[3,5,1,4,2,7,6], i=6, j=5
⑪16-18行目：i>jなのでループを抜ける
⑫25-30行目：j>=kなので、Last = i-1 = 5、Topは1のまま
従って、「ア」が正解です。

b) (2)選択処理2回目の詳細な動作は以下のようになります。
①選択処理１回目より、Top=1, Last=5
②5行目：Top < Lastなのでループ続行
③6-8行目：Pivot=1, i=1, j=5
④10-15行目：x[i]がPivot以上、x[j]がPivot以下となるまで更新される。i=1 j=3
⑤16-18行目：i<jなのでループ続行
⑥19-23行目：x=[1,5,3,4,2,7,6], i=2, j=2
⑦10-15行目：x[i]がPivot以上、x[j]がPivot以下となるまで更新される。i=2, j=1
⑧16-18行目：i>jなのでループを抜ける
⑨25-30行目：i<=kなので、Top = j+1 = 2, Lastは5のまま
従って、「ウ」が正解です。

[答] a) ア　b) ウ

[設問2]

c) αの処理は、Pivotの更新を含むのでPivotによるグループ分けが行われるたびに実行されます。設問2の例では、以下の流れでグループ分けが行われます。
①Pivot=2でグループ分け
[1,3,2,4,2,2,2]　→　[1,2,2,4,2,2,3]　→　[1,2,2,4,2,2,3]※　→　[1,2,2,2,4,2,3]
※３番目と６番目を入替えるだけなので配列自体は変化なし
Top = 1, Last = 4
②更にPivot=2でグループ分け
[1,2,2,2,4,2,3]　→　[1,2,2,2,4,2,3]
※２番目と４番目を入替えるだけなので配列自体は変化なし
Top = 4, Last = 2
以上よりPivotの更新は二回行われるので「イ」が正解です。

d) γの処理は配列の入替えを行う処理なので上記c)の説明より４回入替えが実行されるので「エ」が正解です。

[答] c) イ　d) エ

[設問3]

e) 配列の要素が全て1の場合、Pivotも1となり、x[i]<=Pivotの条件判定が配列の最後まで真となってしまうため、配列の範囲を超えて参照してしまいます。よって「オ」が正解です。

f) 配列x=[1,3,2,4,2,2]の場合は、Pivot=2でグループ分けを行った結果、
x=[1,2,2,2,4,3], i=5, j=4となって一旦ループを抜けます。
そして、Top=1、Last=4に更新して再びループに入りますが、ここでx[i]<=Pivotの条件判定よりi=5、j=4となり再度ループを抜けます。以降同じ処理が繰り返されることになるため「エ」が正解です。

[答] e) オ　f) エ

上記の解説は問題と解答を元に自分なりの考え方を記述しており、間違っている部分もあるかと思いますので、ご了承願います。また、誤りについては正しい考え方をご指摘・ご教授頂けると助かります。