次の手順はシェルソートによる整列を示している。
データ列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)に戻る。
正答1
解説
正解は1です。
シェルソートの手順をデータ数に当てはめ、間隔Hがどう変わるかを追う問題です。
手順(3)が実行されるたびにHが3分の1（小数点以下切捨て）になり、0になったら終わります。
【計算】
データは7，2，8，3，1，9，4，5，6の9個です。
手順(1)で、H＝[9÷3]＝3とします。
手順(2)で、3要素おきの部分列をそれぞれ挿入法で整列します。
手順(3)の1回目で、H＝[3÷3]＝1になります。
手順(4)でHは0ではないので、手順(2)に戻り、全体を挿入法で整列します。
手順(3)の2回目で、H＝[1÷3]＝0になります。
手順(4)でHが0なので整列は完了します。
手順(3)の実行回数は2回です。
【選択肢別解説】
1：○ Hは3、1、0と変わり、手順(3)はHを1にするときと0にするときの2回実行されます。
2：× 3回とすると、手順(1)の計算も手順(3)に数えています。
手順(1)と手順(3)は別の手順です。
3：× 4回になる手順の流れはありません。
Hは2回目の手順(3)で0になり、そこで終了します。
4：× 5回もHの変化と一致しません。
データの並び方に関係なく、回数はデータ数9からHの変化だけで決まります。
【ポイント】
シェルソートは、離れた要素どうしをおおまかに整列してから間隔を詰め、最後に間隔1の挿入法で仕上げる方法です。
この種の問題では、データの中身ではなく間隔Hの変化だけを追えば答えが出ます。