【問題】
次の手順はシェルソートによる整列を示している。データ列7,2,8,3,1,9,4,5,6を手順(1)～(4)に従って整列するとき、手順(3)を何回繰り返して完了するか。ここで、[]は小数点以下を切り捨てた結果を表す。
〔手順〕
(1) [データ数÷３] → Ｈとする。
(2) データ列を互いにＨ要素文だけ離れた要素の集まりからなる部分列とし、それぞれの部分列を、挿入法を用いて整列する。
(3) [Ｈ÷３] → Ｈとする。
(4) Ｈが０であればデータ列の整列は完了し、０でなければ(2)に戻る。
【解答】
実際に当てはめてみれば良い。
データ列の個数は7,2,8,3,1,9,4,5,6の9個だから、
(1) ９÷３ ＝ ３となる。
(2) {7,3,4},{2,1,5},{8,9,6}という部分列として、それぞれを整列すると{3,4,7},{1,2,5},{6,8,9}→{3,1,6,4,2,8,7,5,9}となる。
(3) ３÷３ ＝ １となる。
(4) Ｈは１なので(2)に戻る。
(2) 1要素だけ離れた部分列とは、すなわち{3,1,6,4,2,8,7,5,9}を全てソートすることと同じだから、{1,2,3,4,5,6,7,8,9}になる。
(3) １÷３ ＝ ０．３３…となり、小数点を切り捨てるから、＝０となる。
(4) Ｈが０なので、データ列の整列は終了となる。
よって、(1)→(2)→(3)→(4)→(2)→(3)→(4)の流れとなり、(3)の手順は2回使用されているから、解答は2回となる。
この問題は、(2)の中身の処理が分からなくても、Ｈの値さえしっかりと理解していれば解答にたどり着くことが出来る。問題文を見て、すぐにあきらめないことが重要になる。