次の手順はシェルソートによる整列を示している。
データ列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 |
答え ア
【解説】
問題の整列するデータ列の要素の数は9個であるので、まず最初に(1)の処理で“9÷3 = 3”で「H = 3」になる。
次に(2)の処理があるが、ここでH の値には変化がないので処理の説明は省略して(3)に進み、“3÷3 = 1”で「H = 1」になり、(4)でH は0でないので(2)に進む。
(2)の処理ではH の値に変化がないので処理の説明は省略して(3)に進み、“1÷3 = 0”で「H = 0」になり、(4)でH が0なので終了する。
結果、(3)の処理は2回(ア)行われた。
【キーワード】
・ソート