第２種情報処理技術者試験 2000年度 ＝ 平成12年度・秋期 午前 問13

　次の手順はシェルソートによる整列を示している。データ列“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

解答

　ア

解説

　シェルソートは、ある間隔で要素を取り出した部分列を整列し、更に間隔をつめた部分列を取り出して整列する方法です。
　本問では、データ数を３で割っていきますので、
　　　［９÷３］→３　　３ソート（３要素離れたものをソート）
　　　［３÷３］→１　　１ソート（１要素離れたもの＝全体をソート）
と、２回のソートで全体のソートが完了します。

■１回目■

　H = [9÷3] = 3 → ３ソートを実行


　　　　　　　　┌─────┬─────┐
　　　　　　┌─────┬─────┐
　　　　┌─────┬─────┐
　　　┌─┬─┬─┬─┬─┬─┬─┬─┬─┐
　　　│７│２│８│３│１│９│４│５│６│
　　　└─┴─┴─┴─┴─┴─┴─┴─┴─┘
　　　　　　　　　　　　　↓　赤・青・緑をそれぞれソート
　　　┌─┬─┬─┬─┬─┬─┬─┬─┬─┐
　　　│３│１│６│４│２│８│７│５│９│
　　　└─┴─┴─┴─┴─┴─┴─┴─┴─┘


■２回目■

　H = [3÷3] = 3 → １ソートを実行



　　　　┌─┬─┬─┬─┬─┬─┬─┬─┐
　　　┌─┬─┬─┬─┬─┬─┬─┬─┬─┐
　　　│３│１│６│４│２│８│７│５│９│
　　　└─┴─┴─┴─┴─┴─┴─┴─┴─┘
　　　　　　　　　　　　　↓　赤をソート
　　　┌─┬─┬─┬─┬─┬─┬─┬─┬─┐
　　　│１│２│３│４│５│６│７│８│９│
　　　└─┴─┴─┴─┴─┴─┴─┴─┴─┘


BohYoh.comトップページへ