応用情報技術者 2012年 春期 午前2 問07
問題文
次の手順はシェルソートによる整列を示している。データ列 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＝3、次にHは3÷3＝1、さらに1÷3＝0となり0で終了。
- 差がつくポイント：Hの更新と切り捨て計算を正確に理解し、繰り返し回数を数えることが重要です。
正解の理由
手順(1)でHを9÷3＝3と設定し、手順(3)でHを3÷3＝1に更新します。
次に再度手順(3)でHを1÷3＝0に更新し、0になったため整列完了です。
よって手順(3)は2回繰り返されます。これが正解の理由です。
次に再度手順(3)でHを1÷3＝0に更新し、0になったため整列完了です。
よって手順(3)は2回繰り返されます。これが正解の理由です。
よくある誤解
Hの更新時に小数点以下を切り捨てることを忘れ、繰り返し回数を多く数えてしまうことがあります。
また、初期Hの計算を誤ると全体の繰り返し回数もずれてしまいます。
また、初期Hの計算を誤ると全体の繰り返し回数もずれてしまいます。
解法ステップ
- データ数9を3で割り、初期Hを計算する（9÷3＝3）。
- Hを使って部分列を挿入法で整列する（手順(2)）。
- Hを3で割り、小数点以下切り捨てで更新する（3÷3＝1）。
- Hが0でなければ手順(2)に戻る。
- 再度Hを3で割り切り捨てる（1÷3＝0）と0になるので終了。
- 手順(3)の繰り返し回数は2回と判定する。
選択肢別の誤答解説
- ア: 2
正解。Hの更新を正しく理解し、2回繰り返すことを示している。 - イ: 3
Hの更新回数を1回多く数えてしまった誤り。 - ウ: 4
Hの計算を誤り、繰り返し回数を過大評価している。 - エ: 5
Hの更新を繰り返しすぎてしまい、実際の手順と合わない。
補足コラム
シェルソートは挿入ソートの改良版で、間隔Hを徐々に小さくして整列を進めます。
間隔Hの選び方や更新方法は性能に大きく影響し、今回のようにで更新する方法は基本的な手法の一つです。
小数点以下の切り捨てを正確に行うことが重要です。
間隔Hの選び方や更新方法は性能に大きく影響し、今回のようにで更新する方法は基本的な手法の一つです。
小数点以下の切り捨てを正確に行うことが重要です。
FAQ
Q: なぜHを3で割るのですか？
A: シェルソートの間隔を徐々に狭めるためで、3で割ることで効率的に整列を進めます。
A: シェルソートの間隔を徐々に狭めるためで、3で割ることで効率的に整列を進めます。
Q: 小数点以下を切り捨てる理由は？
A: 配列のインデックスは整数なので、間隔Hも整数にする必要があるためです。
A: 配列のインデックスは整数なので、間隔Hも整数にする必要があるためです。
関連キーワード: シェルソート、挿入法、整列アルゴリズム、小数点切り捨て、繰り返し回数
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！