[C#][VB] 挿入ソートを実装する

挿入ソート

挿入ソートを C#, VB.NET で実装してみます。

挿入ソートは、時間計算量 O(n^2) でバブルソートや選択ソートと同じく高速なソートアルゴリズムとは言えません。ただし、挿入ソートについて言えばある面で有用なソートアルゴリズムです。

挿入ソートは要素数の少ないデータに対して、効率よくソートするアルゴリズムです。

クイックソートなど高速なソートアルゴリズムについては、処理のオーバーヘッドが発生するため、少数のデータを対象にしたソートだと。

さらに挿入ソートには、ほぼソート済のデータに対して高速に動作します。これら挿入ソートの特性を生かし、ある程度の範囲まで高速なソートアルゴリズム(クイックソートやマージソート)を利用し、要素数が少なくなった段階で挿入ソートに切り替えるという手法が考えられます。
挿入ソートは 安定 な 内部 ソートです。

アルゴリズム

考え方としては「ソート済の配列に対してデータを適切な位置に挿入しながらソートする」というものです。

要素数 n の配列を挿入ソートでソートする場合の手順は以下の通りです。

1. 配列の先頭要素をソート済とします。
2. i=1..n までの範囲でループし、i番目の要素を挿入します。

挿入の考え方

例えばソート済のデータが2つあって、そこに 2 を挿入する場面を考えます。_ は挿入候補の位置です。

1 3 _

まず 2 と ソート済末尾の 3 を比較します。3のほうが大きいので1つ後ろにずらします。

1 _ 3

次に1と2を比較します。1のほうが小さいので挿入場所は現在の位置に決定します。

1 2 3

挿入先にデータを入れて挿入処理が完了します。

挿入時にバブルソートのように都度交換処理を入れると余計な代入処理が増えて処理が遅くなります。交換ではなく、挿入候補のデータを退避し、要素をずらしながら挿入先を探しましょう。

C#

実装します。

public static void InsertSort<T>(T[] a) where T : IComparable<T>
{
    // a[i] をソート済の a[0]..a[i-1] に挿入する
    for (int i = 1; i < a.Length; i++)
    {
        // 挿入対象のデータを退避
        var tmp = a[i];

        // 挿入先のインデックスを探す
        var j = i - 1;
        while (j >= 0 && tmp.CompareTo(a[j]) < 0)
        {
            // 交換ではなく後ろにずしていく
            a[j + 1] = a[j];
            j -= 1;
        }

        // 挿入
        a[j + 1] = tmp;
    }
}

VB.NET

Public Shared Sub InsertionSort(Of T As IComparable)(a As T())
    For i = 1 To a.Length - 1
        Dim tmp = a(i)
        Dim j = i - 1
        While j >= 0 AndAlso tmp.CompareTo(a(j)) < 0
            a(j + 1) = a(j)
            j -= 1
        End While
        a(j + 1) = tmp
    Next
End Sub

以上。