応用情報技術者 2019年 春期 午前2 問06
問題文
次の手順はシェルソートによる整列を示している。データ列 7, 2, 8, 3, 1, 9, 4, 5, 6を手順(1)〜(4) に従って整列するとき、手順 (3) を何回繰り返して完了するか。ここで、[ ]は小数点以下を切り捨てた結果を表す。
〔手順〕
(1) [データ数÷3] → Hとする。
(2) データ列を、互いにH 要素分だけ離れた要素の集まりからなる部分列とし、それぞれの部分列を、挿入法を用いて整列する。
(3) [H÷3] → H とする。
(4) Hが0であればデータ列の整列は完了し、0でなければ(2)に戻る。
選択肢
ア：2（正解）
イ：3
ウ：4
エ：5
シェルソートの繰り返し回数計算【午前2 解説】
要点まとめ
- 結論：手順(3)の繰り返し回数は「2回」である。
- 根拠：初期のHはデータ数9を3で割り切り、次にHを3で割り続けると2回目で0になるため。
- 差がつくポイント：Hの更新方法と切り捨て計算を正確に理解し、繰り返し回数を正しく数えることが重要。
正解の理由
手順(1)でHを「データ数÷3」で求めると、9÷3=3となります。
手順(3)でHを「H÷3」で更新し、切り捨てるため、1回目の更新は3÷3=1、2回目は1÷3=0となり、2回繰り返すとHが0になり整列完了です。
したがって、手順(3)の繰り返し回数は2回で、選択肢の中ではア: 2が正解です。
手順(3)でHを「H÷3」で更新し、切り捨てるため、1回目の更新は3÷3=1、2回目は1÷3=0となり、2回繰り返すとHが0になり整列完了です。
したがって、手順(3)の繰り返し回数は2回で、選択肢の中ではア: 2が正解です。
よくある誤解
Hの更新を「H÷3」ではなく「3で割った余り」や「小数点以下を切り上げる」と誤解し、繰り返し回数を多く数えてしまうことがあります。
解法ステップ
- データ数9を3で割り、初期Hを求める → H=3
- Hが0でなければ手順(2)の挿入法整列を行う
- Hを3で割り、切り捨てる → 3÷3=1
- Hが0でなければ手順(2)に戻る
- 再度Hを3で割り、切り捨てる → 1÷3=0
- Hが0になったため整列完了、繰り返し回数は2回
選択肢別の誤答解説
- イ: 3 → Hの更新を誤り、余計に繰り返した結果。
- ウ: 4 → Hの計算方法を誤解し、繰り返し回数を過大評価。
- エ: 5 → 同様にHの更新ルールを誤解し、回数を多く見積もった誤答。
補足コラム
シェルソートは挿入ソートの改良版で、間隔Hを徐々に小さくしながら部分列を整列します。Hの選び方によって性能が大きく変わり、今回のように「データ数÷3」を基準にする方法は基本的なギャップ列の一例です。
FAQ
Q: なぜHを3で割るのですか？
A: シェルソートのギャップ列を徐々に小さくし、最終的に1（通常の挿入ソート）に近づけるためです。
A: シェルソートのギャップ列を徐々に小さくし、最終的に1（通常の挿入ソート）に近づけるためです。
Q: 小数点以下を切り捨てる理由は？
A: ギャップは整数でなければならず、切り捨てにより確実に値を減らしていくためです。
A: ギャップは整数でなければならず、切り捨てにより確実に値を減らしていくためです。
関連キーワード: シェルソート、挿入法、ギャップ列、整列アルゴリズム、切り捨て、繰り返し回数
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！