次の手順はシェルソートによる整列を示している。
データ列7，2，8，3，1，9，4，5，6を手順(1)〜(4)に従って整列するとき，手順(3)を何回繰り返して完了するか。
ここで，［ ］は小数点以下を切り捨てた結果を表す。
〔手順〕
(1) “H←［データ数÷3］”とする。
(2) データ列を，互いにH要素分だけ離れた要素の集まりから成る部分列とし，それぞれの部分列を，挿入法を用いて整列する。
(3) “H←［H÷3］”とする。
(4) Hが0であればデータ列の整列は完了し，0でなければ(2)に戻る。
正答1
解説
正解は1です。
シェルソートは、一定間隔Hごとの部分列を挿入法で整列し、Hを小さくしながら繰り返す方法です。
この問題は、手順(3)が何回実行されるかを数えるだけで、データの中身は回数に影響しません。
【計算】
データ数は9なので、手順(1)でH＝［9÷3］＝3です。
手順(2)でH＝3の部分列を整列します。
手順(3)の1回目で、H＝［3÷3］＝1になります。
手順(4)でHは0でないので、手順(2)に戻ります。
手順(2)でH＝1として全体を挿入法で整列します。
手順(3)の2回目で、H＝［1÷3］＝0になります。
手順(4)でHが0なので完了です。
よって手順(3)は2回繰り返されます。
【選択肢別解説】
1：○ 上の計算のとおり、Hは3、1、0と変わり、手順(3)は2回実行されます。
2：× 3回になるには、Hが0になるまでにもう1段階必要です。
初期値がH＝3なので、Hは1を経てすぐ0になり、3回にはなりません。
3：× 4回は、データ数がもっと多く初期のHが大きい場合の回数です。
データ数9では起こりません。
4：× 5回繰り返すには、初期値のHが3^4以上である必要があります。
データ数9ではH＝3から始まるので、5回にはなりません。
【ポイント】
シェルソートの最後は必ずH＝1の挿入法で、ここで全体の整列が保証されます。
手順をたどる問題は、変数の値を1行ずつ書き出すと確実です。