平成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


答え ア


解説
問題の整列するデータ列の要素の数は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回(ア)行われた。


キーワード
・ソート

キーワードの解説
  • ソート
    データの集合を大きい順や、小さい順で並び替え(整列)することです。
    ソートには代表的な方法(アルゴリズム)として、シェルソート、マージソート、バブルソート、クイックソート、ヒープソート、挿入ソート、選択ソートなどがある。

もっと、「ソート」について調べてみよう。

戻る 一覧へ 次へ