平成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



【正解】 ア

シェルソートは、ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し、
更に間隔を詰めて同様の操作を行い、間隔が1になるまでこれを繰り返すソート方法
である。

解答するにあたり、
(2) については考える必要はないが、一応記載しておく。

7、
、3、、4、

(1) データ数は9だから、 9÷3 = 3→H
(2) [7、3、4] [
] [] の部分列を整列する。
   3、、4、、7、
(3) 3÷3 = 1→H
(4) H=1なので、(2)に戻る。
(2) 間隔が1なので、全体を整列する。
 1、2、3、4、5、6、7、8、9
(3) 1÷3 = 0→H
(4) Hが0なので、データ列の整列は完了。

よって、手順(3)は
2回繰り返して完了する。

なお、
9文字を3つの要素でソートするより、
8文字を2つの要素でソートする方がシェルソートを理解しやすい。
7、
、1、 でシェルソートする。

(1) データ数は8だから、 8÷2 = 4→H
(2) [7、1] [
] [] [] の部分列を整列する。
 1、、7、 
(3) 4÷2 = 2→H
(4) H=2なので、(2)に戻る。
(2) [1、
、7、] [] の部分列を整列する。
 1、
、7、
(3) 2÷2 = 1→H
(4) H=1なので、(2)に戻る。
(2) 間隔が1なので、全体を整列する。
 1、2、3、4、5、6、7、8、9
(3) 1÷3 = 0→H
(4) Hが0なので、データ列の整列は完了。

EXCEL VBAのご相談なら ファーストマクロ 



問6 目次 問8
ファーストマクロ TOPページ