問６
次の手順はシェルソートによる整列を示している。データ列７、２、８、３、１、９、４、５、６を手順(1)～(4) に従って整列するとき、手順 (3)
を何回繰り返して完了するか。ここで、[ ] は小数点以下を切り捨てた結果を表す。
〔手順〕
(1) “Ｈ←[データ数÷３]”とする。
(2) データ列を、互いにＨ要素分だけ離れた要素の集まりからなる部分列とし、それぞれの部分列を、
挿入法を用いて整列する。
(3) “Ｈ←[Ｈ÷３]”とする。
(4) Ｈが０であればデータ列の整列は完了し、０でなければ (2) にもどる。
ア ２ イ ３ ウ ４ エ ５
正解
ア
解説
シェルソートは、ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、間隔が１になるまでこれを繰り返すソート方法である。
解答するにあたり、
(2) については考える必要はないが、一応記載しておく。
７、２、８、３、１、９、４、５、６
(1) データ数は９だから、 ９÷３ ＝ ３→Ｈ
(2) [７、３、４] [２、１、５] [８、９、６] の部分列を整列する。
３、１、６、４、２、８、７、５、９
(3) ３÷３ ＝ １→Ｈ
(4) Ｈ＝１なので、(2)に戻る。
(2) 間隔が１なので、全体を整列する。
１、２、３、４、５、６、７、８、９
(3) １÷３ ＝ ０→Ｈ
(4) Ｈが０なので、データ列の整列は完了。
よって、手順(3)は２回繰り返して完了する。
なお、
９文字を３つの要素でソートするより、
８文字を２つの要素でソートする方がシェルソートを理解しやすい。
７、２、８、３、１、９、４、５ でシェルソートする。
(1) データ数は８だから、 ８÷２ ＝ ４→Ｈ
(2) [７、１] [２、９] [８、４] [３、５] の部分列を整列する。
１、２、４、３、７、９、８、５
(3) ４÷２ ＝ ２→Ｈ
(4) Ｈ＝２なので、(2)に戻る。
(2) [１、４、７、８] [２、３、９、５] の部分列を整列する。
１、２、４、３、７、５、８、９
(3) ２÷２ ＝ １→Ｈ
(4) Ｈ＝１なので、(2)に戻る。
(2) 間隔が１なので、全体を整列する。
１、２、３、４、５、７、８、９
(3) １÷３ ＝ ０→Ｈ
(4) Ｈが０なので、データ列の整列は完了。
