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

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

解答：ア

＜解説＞

[手順]に沿って、シュミレートする。

	(1)	データの個数は9である。[9÷3]=3であり、H=3となる
	(2)	データ列を部分列とみなし、それぞれ整列する(整列過程は手順(3)の実行回数には影響しない)
	(3)	H=[H÷3}=[3÷3]=1となる
	(4)	H≠0なので(2)へ戻る
	(2)	データ列を部分列とみなし、それぞれ整列する
	(3)	H=[H÷3}=[1÷3]=0(小数点以下切捨て)となる
	(4)	H=0なので処理を終了する。

処理を終了するまでに、(3)の処理は2回ある。したがって、アが正解である。

キーワード

• 「シェルソート」関連の過去問題・・・シェルソートとは
  • 応用情報技術者 平成24年度(春季) 問7