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