応用情報技術者試験 2012年度 ＝ 平成24年度・春期 午前 問7

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