選択ソートと挿入ソートの違い
両者を同一視している方が多い上に、ぱっと見アルゴリズムが似ているこの2つ。
実は結構差があるので詳しく見てみましょう。
アルゴリズム
ふたつのアルゴリズムの詳細については wikipedia がそこそこ詳しいのでそちらを参照してください。
挿入ソート
挿入ソートは「既にソート済みのデータ列に対して、新しい要素を正しい位置に挿入する」ことを繰り返していくアルゴリズムです( wikipedia:挿入ソート )。
選択ソート
対して、選択ソートは「整列されていない最小(最大)の要素を1つ取り出し、整列済みデータの末尾に加える」操作を繰り返していくアルゴリズムです(wikipedia:選択ソート)。
計算量
平均計算量、最悪計算量はどちらも です。
ところが、最良計算量は挿入ソートが に対して、選択ソートはになります。ここについて詳しく見てみましょう*1。
以下では昇順にソートすることを前提としています。
n個の要素があり、既にソート済みの要素がm個あるとします(もちろん )。つまり、ある時点でソートされていないデータは 個です。
挿入ソート
1番目のデータは、比較するまでもなく挿入位置が決定できます。2番目以降のデータは、ソート済みの各要素と比較して挿入する場所を決める必要があります。
最短の場合だと、1回の比較で挿入位置が決定できますが、最悪m回の比較が必要です。要素がランダムであると仮定すれば、平均 回の比較が必要です*2。
平均計算量
さて、ある時点でソートされていないデータはm個あり、mは1から(n-1)まで増加していくので、比較回数は次のようになります。
これは次のように書けます。
ということで、平均計算量は です。
最悪計算量
最悪の場合は常にm回の比較が必要なので、
となります。よって、最悪計算時間もです(分母が変わっていますけどね)。
最良計算時間
最良の場合は、常に1回の比較のみで挿入位置が決まる、つまりソート済みのデータをソートする場合です。1回の比較をn-1回繰り返すのですから
となり、 最良計算時間は です。
選択ソート
次に、選択ソートを見てみましょう。選択ソートでは、まず1つのデータの位置を確定するために 回の比較が必要です。
次は比較対象のデータが1つ減っているので、回の比較が必要です。これを繰り返していくので、
となりますが、これは要するに1からn-1までの総和を求めているだけなので、
と表せます。比較回数は最良の場合も最悪の場合も常に同じなので、入力によらず計算量は です。
まとめ
オーダを見ると、挿入ソートは最良の場合 でソートできるというメリットがあります。最悪の場合でも選択ソートと同じですし、基本的には挿入ソートを選ぶべき*3です。
「整列済みのデータに新しい要素を加える」といった場面では、挿入ソートは非常に高速に動作するので非常に便利です。また、ほとんど整列済みのデータに対しても早いので、他のソートアルゴリズム(例えばクイックソート)でおおまかにソートしたあと、最後に挿入ソートを使うといった手法もあります。データの種類にもよりますが、クイックソートの場合は要素数が7〜30くらいになったら挿入ソートに切り替えたほうが早くなります。クイックソートは確かに高速なアルゴリズムですが、オーバーヘッドが大きいので小さいデータに対しては なアルゴリズムが早いことがあるのです。
また、リストは挿入が でできるので、特に挿入ソートが効果的になります。
どちらも安定なソートで内部ソートという点では同じですし、先程も触れた通り選択ソートよりは挿入ソートのほうが優れていると言えます。