教育統括部

7月26日に行われた午前免除試験より，アルゴリズムの問題を取り上げましょう。

基本情報技術者試験ではソートや探索の問題がよく出ます。単純ソートは当然必ず覚える必要がありますが，シェルソート，クイックソート，ヒープソートなども概要は把握しておきましょう。

問5
次の手順はシェルソートによる整列を示している。データ列7,2,8,3,1,9,4,5,6を手順(1)～(4)に従って整列するとき，手順(3)を何回繰り返して完了するか。ここで，[ ]は小数点以下を切り捨てた結果を表す。

[手順]
(1)[データ数÷3]→Hとする。
(2)データ列を互いにH要素分だけ離れた要素の集まりからなる部分列とし，それぞれの部分列を，挿入法を用いて整列する。
(3)[H÷3]→Hとする。
(4)Hが0であればデータ列の整列は完了し，0でなければ(2)に戻る。

ア　2
イ　3
ウ　4
エ　5

答え　ア
解説　全く見掛け倒しの問題です。(2)の手順でHが変わらないことに注意すると，手順(2)でどんな処理が行われるかは問題にならず，単にHがどう変わるかだけ気にすればよいです。データ数が9個ですからHは初めは3で，次は1になり，次に0となって終了。したがって手順(3)は2回繰り返します。
答えには直接関係ありませんが，この手順でデータ列をソートすると次のようにデータ列が変化していきます。
(初期状態)7,2,8,3,1,9,4,5,6
((3)1回目)3,1,6,4,2,8,7,5,9
((3)2回目)1,2,3,4,5,6,7,8,9


問6ヒープソートの説明として，適切なものはどれか。
ア　ある間隔おきに取り出した要素からなる部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が1になるまでこれを繰り返す。
イ　中間的な基準値を決めて，それよりも大きな値を集めた区分と，小さな値を集めた区分に要素を振り分ける。次に，それぞれの区分の中で同様な処理を繰り返す。
ウ　隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。
エ　未整列の部分を順序木にして，そこから最小値を取り出して整列済みの部分に移す。この操作を繰り返して，未整列の部分を縮めていく。

答え　エ

解説　前問でわかりますがアはシェルソート。イはクイックソート。ウはバブルソート。