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

両者を同一視している方が多い上に、ぱっと見アルゴリズムが似ているこの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)$ でできるので、特に挿入ソートが効果的になります。