平成31年度 春期 午前 問6

✓ これが正解ア2

解説

H を 3 で割り、0 になるまで進めます。

シェルソートは、離れた位置にある要素どうしを部分列に分けて整列し、間隔 H を狭めながら整えていく方法です。設問は間隔 H を 3 で割って更新する手順を何度通るかを尋ねています。要素数が 9 なので初回は H を 9 割る 3 で 3 とし、この H で部分列を整えます。次に手順が H を 3 で割ると 1 になるので、これで一度目です。1 の間隔でもう一度整えたあと、また 3 で割って 0 になり、これで二度目となります。0 になった時点で判定手順が完了と判断して終わるため、割り算を通る回数は二度です。

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

• イ3：3 回になるのは、間隔を最初に 9 から作るところを別の手順に数え違えたときです。設問は開始時に H を要素数の 3 分の 1 に定めており、そこは判定を伴う繰り返しの通過に入りません。
• ウ4：4 回になるのは、H が 0 になった後にもう一度部分列を整える工程を数えたときです。0 に達すると判定手順で完了と決まるため、その後に整列の工程は現れません。
• エ5：5 回は、手順 (3) を通る回数としては多すぎる値です。設問はあくまで 3 で割って更新するので、3、1、0 の三段だけで進み、5 段には届きません。