情報処理安全確保支援士試験 情報処理安全確保支援士試験 平成31年度春期 午前Ⅰ 問3: 次の手順はシェルソートによる整列を示している。データ列 7，2，8，3，1，9，4，5，6 を手順(1)〜(4)に従って整列するとき，手順(3)を何回繰り返して

問題本文

次の手順はシェルソートによる整列を示している。データ列 7，2，8，3，1，9，4，5，6 を手順(1)〜(4)に従って整列するとき，手順(3)を何回繰り返して完了するか。ここで，[ ] は小数点以下を切り捨てた結果を表す。 〔手順〕 (1) “H ← [データ数÷3]”とする。 (2) データ列を，互いに H 要素分だけ離れた要素の集まりから成る部分列とし，それぞれの部分列を，挿入法を用いて整列する。 (3) “H ← [H÷3]”とする。 (4) H が0であればデータ列の整列は完了し，0でなければ(2)に戻る。

選択肢

• ア.2
• イ.3
• ウ.4
• エ.5

正解

ア. 2

解説

シェルソートは間隔Hを徐々に縮めて挿入法を繰り返す整列法。データ数9でH←[9÷3]=3から開始し、手順(2)で整列後、手順(3)でH←[3÷3]=1、続いて手順(3)でH←[1÷3]=0となり完了する。手順(3)の実行は2回。よってアが正解。間隔を大きくとって粗く整列してから細かくすることで、単純挿入法より高速になる仕組みを問うている。

選択肢ごとの解説

• ア.H=3→1→0と手順(3)を2回実行した時点でH=0となり整列完了。回数2で正解。
• イ.3回では計算が合わない。Hは3,1,0と推移し2回目で0になるため誤り。
• ウ.4回は過大。[H÷3]は3→1→0と速やかに0へ収束し、手順(3)は2回で済むため誤り。
• エ.5回はさらに過大で、Hが3,1,0と推移する減少手順に一致しないため誤り。