令和元年度 高度共通 午前I（PM試験） 問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
解答・解説を見る
正解：ア
AI解説
データ数は9なので、手順(1)でH=[9÷3]=3となる。以降、(2)整列→(3)H=[3÷3]=1→(4)H≠0なので(2)へ→(2)整列→(3)H=[1÷3]=0→(4)H=0で完了。手順(3)が実行されたのはH:3→1とH:1→0の2回である。 ア: 正解。手順(3)はH=1になるときとH=0になるときの計2回実行されて整列が完了する。 イ: 3回は、手順(1)の初期設定も(3)の実行回数に数えてしまった場合などの誤答である。 ウ: 4回は、Hの更新規則を[H÷2]などと誤解した場合の誤答である。 エ: 5回は、手順のループ回数を要素数などと混同した誤答である。 💡 シェルソートは「間隔Hを徐々に狭めながら挿入ソートを繰り返す」手法。この種の問題はデータの中身を追う必要はなく、Hの値の変化(3→1→0)だけを機械的にトレースすればよい。
出典：令和元年度 秋期 プロジェクトマネージャ試験 午前I 問3 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。