読者です 読者をやめる 読者になる 読者になる

Sideswipe

情報工学、計算論的神経科学など、真面目なこと書くブログ。お仕事の話は Twitter: @kazoo04 にお願いします。

選択ソートと挿入ソートの違い

両者を同一視している方が多い上に、ぱっと見アルゴリズムが似ているこの2つ。
実は結構差があるので詳しく見てみましょう。

アルゴリズム

ふたつのアルゴリズムの詳細については wikipedia がそこそこ詳しいのでそちらを参照してください。

挿入ソート

挿入ソートは「既にソート済みのデータ列に対して、新しい要素を正しい位置に挿入する」ことを繰り返していくアルゴリズムです( wikipedia:挿入ソート )。

選択ソート

対して、選択ソートは「整列されていない最小(最大)の要素を1つ取り出し、整列済みデータの末尾に加える」操作を繰り返していくアルゴリズムです(wikipedia:選択ソート)。

計算量

平均計算量、最悪計算量はどちらも O(n^2) です。
ところが、最良計算量は挿入ソートが O(n)に対して、選択ソートはO(n^2)になります。ここについて詳しく見てみましょう*1
以下では昇順にソートすることを前提としています。

n個の要素があり、既にソート済みの要素がm個あるとします(もちろん n \geq m)。つまり、ある時点でソートされていないデータは  n-m個です。

挿入ソート

1番目のデータは、比較するまでもなく挿入位置が決定できます。2番目以降のデータは、ソート済みの各要素と比較して挿入する場所を決める必要があります。
最短の場合だと、1回の比較で挿入位置が決定できますが、最悪m回の比較が必要です。要素がランダムであると仮定すれば、平均 \frac{m}{2} 回の比較が必要です*2

平均計算量

さて、ある時点でソートされていないデータはm個あり、mは1から(n-1)まで増加していくので、比較回数は次のようになります。

\frac{1}{2} + \frac{2}{2} + \frac{3}{2} + ... + \frac{n-1}{2} = \displaystyle \sum_{i=1}^{n-1} \frac{i}{2} = \frac{1}{2} \displaystyle \sum_{i=1}^{n-1}{i}

これは次のように書けます。

\frac{1}{2} \displaystyle \sum_{i=1}^{n-1}{i} = \frac{1}{2}  \cdot \frac{n(n-1)}{2} = \frac{1}{2} \cdot \frac{n^2-n}{2} = \frac{n^2-n}{4}

ということで、平均計算量は  O(n^2) です。

最悪計算量

最悪の場合は常にm回の比較が必要なので、

 1 + 2+ 3 + ... + (n-1) = \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = \frac{n^2-n}{2}

となります。よって、最悪計算時間も O(n^2)です(分母が変わっていますけどね)。

最良計算時間

最良の場合は、常に1回の比較のみで挿入位置が決まる、つまりソート済みのデータをソートする場合です。1回の比較をn-1回繰り返すのですから

 \displaystyle \sum_{i=1}^{n-1} 1 = n - 1

となり、 最良計算時間は  O(n) です。

選択ソート

次に、選択ソートを見てみましょう。選択ソートでは、まず1つのデータの位置を確定するために  (n-1) 回の比較が必要です。
次は比較対象のデータが1つ減っているので、 (n-2) 回の比較が必要です。これを繰り返していくので、

 (n-1)+(n-2)+...+(n-(n-2))+(n-(n-1)) = (n-1) + (n-2) + ... + 2 + 1

となりますが、これは要するに1からn-1までの総和を求めているだけなので、

 \displaystyle \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = \frac{n^2-n}{2}

と表せます。比較回数は最良の場合も最悪の場合も常に同じなので、入力によらず計算量は  O(n^2) です。

まとめ

オーダを見ると、挿入ソートは最良の場合  O(n) でソートできるというメリットがあります。最悪の場合でも選択ソートと同じですし、基本的には挿入ソートを選ぶべき*3です。

「整列済みのデータに新しい要素を加える」といった場面では、挿入ソートは非常に高速に動作するので非常に便利です。また、ほとんど整列済みのデータに対しても早いので、他のソートアルゴリズム(例えばクイックソート)でおおまかにソートしたあと、最後に挿入ソートを使うといった手法もあります。データの種類にもよりますが、クイックソートの場合は要素数が7〜30くらいになったら挿入ソートに切り替えたほうが早くなります。クイックソートは確かに高速なアルゴリズムですが、オーバーヘッドが大きいので小さいデータに対しては  O(n^2) なアルゴリズムが早いことがあるのです。

また、リストは挿入が  O(1) でできるので、特に挿入ソートが効果的になります。

どちらも安定なソートで内部ソートという点では同じですし、先程も触れた通り選択ソートよりは挿入ソートのほうが優れていると言えます。

*1:厳密な意味での計算量を計算しているわけではないので注意、雰囲気だけです

*2:交換回数は常に比較回数より少ないので、以下では比較回数についてのみ考えている

*3:選択ソートのほうが優れている点をご存じの方がいたら教えてください