次の手順はシェルソートによる整列を示している。データ列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、2、8、3、1、9、4、5、6
(1) データ数は9だから、9÷3 ＝ 3 → H
(2) [7、3、4] [2、1、5] [8、9、6] の部分列を整列する。
3、1、6、4、2、8、7、5、9
(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、2、8、3、1、9、4、5 でシェルソートする。
(1) データ数は8だから、 8÷2 ＝ 4 → H
(2) [7、1] [2、9] [8、4] [3、5] の部分列を整列する。
1、2、4、3、7、9、8、5
(3) 4÷2 ＝ 2→ H
(4) H＝2なので、(2)に戻る。
(2) [1、4、7、8] [2、3、9、5] の部分列を整列する。
1、2、4、3、7、5、8、9
(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なので、データ列の整列は完了。
| 問６ | 目次 | 問８ |