問6応用情報技術者 平成31年度 春期

解説

正解は1。データ数は9。手順(1)でH＝[9÷3]＝3とし、手順(2)でH＝3の部分列ごとに挿入法で整列する。手順(3)（1回目）でH＝[3÷3]＝1。手順(4)でHは0でないので(2)に戻り、H＝1、つまり全体を挿入法で整列する。ここで整列は済む。手順(3)（2回目）でH＝[1÷3]＝0となり、手順(4)で完了する。よって手順(3)は2回実行される。

2の3回、3の4回、4の5回は、Hが3→1→0と変わる段数より多く、Hの更新式に合わない。データの並び方にかかわらず、回数はデータ数とHの更新式だけで決まる。

根拠：シェルソートのアルゴリズム（間隔Hを縮めながら部分列を挿入法で整列する）。