シェルソートの手順の繰返し回数
出典: 平成31年度 春期 応用情報技術者試験 午前 問6 (IPA)
次の手順はシェルソートによる整列を示している。データ列 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
正解と解説を見る
正解: ア
- ア: H は 3 → 1 → 0 と変わり、手順 (3) は 2 回実行されるので正しい答えです。
- イ: 手順 (3) は H を 3 → 1、1 → 0 にする 2 回だけです。
- ウ: 手順 (3) は 2 回で H が 0 になり、整列が完了します。
- エ: 手順 (3) は 2 回で H が 0 になり、整列が完了します。
ポイント
データ数は 9 です。
- 手順 (1): H ← [9 ÷ 3] ＝ 3。(2) で間隔 3 の部分列を整列します。
- 手順 (3) 1 回目: H ← [3 ÷ 3] ＝ 1。0 でないので (2) に戻り、間隔 1 (普通の挿入法) で整列します。
- 手順 (3) 2 回目: H ← [1 ÷ 3] ＝ 0。(4) で完了します。
よって手順 (3) は 2 回 です。