整列アルゴリズム(ソート)とその計算量をまとめてみた【応用情報】

情報工学

【応用情報技術者試験・アルゴリズムとプログラミング】

以下では、先頭に最も小さい要素、最後に最も大きい要素が来るように、順番に並べることを考える。

バブルソート

隣り合う2つの要素を比較し、大小順になるように交換する。交換の必要がなくなるまで繰り返す。

計算量

要素数がnのとき、O(n^2)。ただし、計算量は比較回数で評価。

単純選択法

最も小さい要素を先頭に持ってくる。次に、未整列の先頭(先頭から2番目)に次に小さい要素を持ってくる。これを繰り返す。

計算量

要素数がnのとき、O(n^2)。

単純挿入法

未整列要素の先頭の要素を取り出し、その要素を整列済みの列の正しい位置に挿入していく。

計算量

要素数がnのとき、最悪もしくは平均で、O(n^2)であり、最良でO(n)。

クイックソート

基準の軸を定め、その基準より大きな値の要素を集めた部分と、小さな値を集めた部分に分割する。さらに、それぞれの区分で新たに軸を決め、また2つの区分に分ける。これを要素数が1つになるまで繰り返す。

計算量

平均計算量はO(nlog2(n))。基準を最大値か最小値に選んでしまうと、最悪のO(n^2)になる。

ヒープソート

ヒープと呼ばれる、各節の値に「親が持つデータ≦子が持つデータ」という関係を持たせた順序木を作成し、これを基に配列で表現する。次に、ヒープの根、つまり配列の先頭となった最小値を取り出し、ヒープを再構成する。これを繰り返す。

ヒープの再構成は、取り出された根の部分(上の図で2を値に持つ要素)にヒープの最後の要素(12を値に持つ要素)を移動して、根から「親が持つデータ≦子が持つデータ」の関係が成立するように木を再構成する。

計算量

O(nlog2(n))

マージソート

分割と併合(マージ)を繰り返していく整列法。要素列を大きさ1になるまで分割を繰り返して、その後は比較しながら併合していく。

計算量

O(nlog2(n))

参考↓

話題の映画やアニメを見るならU-NEXTがおすすめです!
今なら31日間無料で多数の映画見放題!!
無料体験中に忘れずに解約すればお金はかかりません!
キャンペーン終了前にお早めの登録を!!
※筆者も利用しました( ´∀` )

情報工学
理系リアルタイムをフォローする
理系リアルタイム

コメント

タイトルとURLをコピーしました