応用情報技術者試験 応用情報技術者試験 平成31年度春期 午前 問6: 次の手順はシェルソートによる整列を示している。データ列 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 を更新する手順（3）が何回実行されるかを、H の値を順に計算して数える問題である。データ数は 9 なので、まず H = [9÷3] = 3 が設定される。手順（3）を 1 回目に実行すると H = [3÷3] = 1、2 回目に実行すると H = [1÷3] = 0 となり、ここで手順（4）の判定が H = 0 となって整列が完了する。したがって手順（3）が実行された回数は 2 回であり、アが正解である。