解説

シェルソートは、一定間隔Hだけ離れた要素同士をグループにして挿入法で整列し、間隔Hを徐々に縮めながら整列を繰り返すアルゴリズムです。最初は大きな間隔で大まかに整列し、間隔を狭めていくことで挿入法の弱点（遠くの要素の移動が遅い）を補い、効率を高めます。本問では9個のデータ列に対し、手順(1)でH=[データ数÷3]=[9÷3]=3と初期化します。手順(3)を実行するたびにHが[H÷3]で更新され、手順(4)でH=0になれば完了します。実際に追跡すると、(1)でH=3→(2)で間隔3の整列→(3)でH=[3÷3]=1（1回目）→(4)はH=1≠0なので(2)へ戻る→(2)で間隔1の整列→(3)でH=[1÷3]=[0.33]=0（2回目）→(4)はH=0なので完了。したがって手順(3)を実行した回数は2回であり、選択肢aが正解です。最後はH=1（隣接要素の単純な挿入法）になるため、必ず完全に整列が完成することが保証される点も、シェルソートの仕組みを理解するうえで重要なポイントです。

なぜ他の選択肢は違うのか

選択肢 イ

3回は誤りです。Hの値の遷移は3→1→0であり、手順(3)で値が更新されるのは「3から1へ」と「1から0へ」の2回だけです。3回繰り返すにはHが3→…→0のように4段階で変化する必要がありますが、データ数9（初期H=3）ではそうなりません。Hの更新（手順(3)の実行）回数を1回多く数えてしまった場合に陥る典型的な誤答です。

選択肢 ウ

4回は誤りです。データ数9に対してHは[9÷3]=3から始まり、[3÷3]=1、[1÷3]=0と、わずか2回の更新でH=0に到達します。4回も繰り返すにはHの初期値がもっと大きい（=データ数が多い）必要があり、本問の条件には合いません。各回の[H÷3]の切捨て計算を丁寧に追えば2回と分かります。間隔を縮めながら整列する点がシェルソート特有であり、バブルソートとは比較対象の選び方が根本的に異なります。

選択肢 エ

5回は誤りです。手順(3)の実行回数はHが0になるまでの更新回数に等しく、本問では3→1→0の2回です。5回は明らかに過大で、Hの初期値[データ数÷3]の計算やその後の[H÷3]の切捨ての扱いを誤り、Hが小さくならないと思い込んだ場合などに生じる誤答です。最小値を選んで先頭から順に確定していく動作はシェルソートの間隔を用いた整列とは別物であり、混同しないようにします。

解くときのポイント

シェルソートはHの遷移を順に書き出すのが確実。H=[データ数÷3]から始め、[H÷3]を繰り返してH=0で終了。手順(3)の実行回数＝Hが0に至るまでの更新回数。最後はH=1で必ず整列が完成する。