「平成31年春季午前問6」手順の実践

問題

出典:応用情報技術者平成31年春季午前問6
次の手順はシェルソートによる整列を示している。
データ列「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)に戻る。

ア:2
イ:3
ウ:4
エ:5


解説

このような問題については解説というよりかは、実際にやってみる以上のことはないだろう。

手順1

データ数は9個なので、[9÷3]でHは3になる。

手順2

何言ってるのか意味わからん感じである。
「互いにH要素分だけ離れた要素の集まりから成る部分列」
→「互いにH要素分だけ離れた要素の集まり」
→「部分列である要素の集まり」は、それぞれがH要素分だけ離れた要素から集まってきた。
ってな感じで要約できるだろうか。
まぁ、理解しづらい言い方をするよね。
みんながみんな、3つ離れた要素で集団を構成している、ということである。

すると、以下のようになる。

データ列「7,2,8,3,1,9,4,5,6」

1つ目:「7,3,4」
2つ目:「2,1,5」
3つ目:「8,9,6」

って感じになる。
これって、「3つ離れた」ってあると、3個飛ばさなきゃいけないって解釈できてしまうのが、
なんとも釈然としない感じである。誤解を招くというか、なんというか。

まぁ、そうやって3個飛ばすと、被ってしまう数字が出るから修正は効くのだろうが。

次の手順の挿入法で整列する、とあるが、ここでは小さい順に並べ替えるということができれば問題ない。

1つ目:「3,4,7」
2つ目:「1,2,5」
3つ目:「6,8,9」

手順3(1回目)

手順1にてHには3を代入しているので、H←[3÷3]で1が入る。

手順4

Hは0ではないので手順(2)に戻る。

手順2

今度は1要素離れるだけなので、単純に一つのまとまりができるだけである。
それを小さい順に並べるだけとなる。

「1,2,3,4,5,6,7,8,9」

結果として1から順に並び替わったということになる。
まぁ回答には関係ないけれど。

手順3(2回目)

Hは1でありそれを3で割ると、0となる。今回は小数点を切り捨てた結果となるので。

ってな訳で手順3は2回繰り返された。

答え