平成19年春期ソフトウェア開発技術者午前問11

n 個のデータを整列するとき、比較回数が最悪の場合でO (n²)、最良の場合でO (n )となるものはどれか。

ア	クイックソート		イ	単純選択法
ウ	単純挿入法		エ	ヒープソート

答え　ウ

【解説】

ア	クイックソートは、整列するデータ列から適当な1個のデータを選択し、データ列を選択したデータより、大きいものと、小さいものに分ける。大小に分けたデータ列の中から、適当な値を選択し、同様の処理を行う。これを、データを分割できなくなるまで繰り返し行うことで整列を行う。クイックソートの比較回数は最悪の場合、O (n²)であり、最良の場合は、O (n logn )である。
イ	単純選択法は、整列するデータ列から最小のデータを探して、先頭のデータと比較する。次に、2番目のデータから最後のデータまでのデータ列から、最小のデータを探して、2番目のデータを繰り返す。この処理を、最後のデータまで行うことで整列を行う。単純選択法の比較回数は、O (n²)である。
ウ	単純挿入法は、データ列の1番目のデータと、2番目のデータを入れ替える(整列する)。次に、3番目のデータを整列してある、1番目・2番目のデータに挿入する形で整列する。この処理を、最後のデータまで行うことで整列を行う。単純挿入法の比較回数は、比較回数は最悪の場合、O (n²)であり、最良の場合は、O (n )である。
エ	ヒープソートは、ヒープという2分木の構造にデータを整列する方法です。まず、未整列のデータ列から、1個データを取り出し、2分木の根にします。次に、未整列のデータ列から、1個データを取り出し、2分木の最後に節を追加して加え、加えた節と親の節を比較して、子が親より小さかったら、親と子を交換します。交換したら親の節とその親の節を比べて同じ処理をします。データ列のすべてを加え終わると、ヒープ木が完成です。この場合、根にデータ列の最も小さいものが来ています。ヒープ木からデータを取り出し、ソートを行います。ヒープ木の根を取り出し、ソート済みのデータの先頭に格納します。ヒープ木は最後の節を根に持ってきて、ヒープ木の再構成を行います。再構成の完了したヒープ木から根を取り出し、上記処理を行います。この処理を、最後のデータまで行うことで整列を行う。ヒープソートの比較回数は、O (n logn )である。

情報処理技術者試験の午前の問題では、しばしソートの比較回数を問う問題が出ますので、代表的な比較回数は覚えてください。

ソート法	平均計算時間
バブルソート	O(n²)
マージソート	O(n logn )
シェルソート	O(n^1.25)

【キーワード】
・ソート

【キーワードの解説】

ソート(sort)
データの並び替え(整列)のことで、様々なアルゴリズムがある。
選択肢以外の有名なソートアルゴリズムとしては、バブルソート、マージソート、シェルソートなどがある。
ソートアルゴリズムの性能を示す値として、平均比較回数(O (x ))が使われる。これは、ソートの処理はデータの比較と入れ替えで、コンピュータの処理としてデータの比較に時間がかかるため、比較回数を比べることで、アルゴリズムの性能が判断できるためである。

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

戻る一覧へ次へ