【C#】挿入ソートを実装してみる

はじめに

今回は挿入ソートを実装してみようという記事になります！

挿入ソートはソートのアルゴリズムの一種で、性能はあまり良くないですが実装が簡単なアルゴリズムだと知られています。
ja.wikipedia.org

バブルソートと似た系統だと表現した方が分かりやすいかもしれませんね。

早速みていきましょう。

挿入ソート

挿入ソートのアルゴリズムは以下の動画がめちゃくちゃ分かりやすいのでみてみてください。
www.youtube.com

コード

/// <summary>
/// 挿入ソート
/// </summary>
public static int[] InsertionSort(IEnumerable<int> items)
{
    var nums = items.ToArray();
    var n = nums.Length;

    // n-1回ループ
    for (int i = 1; i < n; i++)
    {
        // aを取り出す
        var a = nums[i];
        var k = i;

        // aより左にある操作済みの任意の箇所にaを挿入
        while (k >= 1 && a < nums[k - 1])
        {
            nums[k] = nums[k - 1];
            k--;
        }

        nums[k] = a;
    }

    return nums;
}

テスト

実際に使ってみるとこんな感じ。

static void Main(string[] args)
{
    var a = new int[] { 2, 4, 1, 3, 7, 6, 5 };

    foreach (var item in InsertionSort(a))
        Console.WriteLine(item);    // 1,2,3,4,5,6,7
}

前：{ 2, 4, 1, 3, 7, 6, 5 }
後：{ 1, 2, 3, 4, 5, 6, 7 }

アルゴリズム考察

挿入ソートの性能を評価するために計算量を考えてみましょう。

一番ステップ数が大きくなってしまうのは降順になっている場合です。

{ 7, 6, 5, 4, 3, 2, 1 }

この場合n-1回のループの中で最悪i回の処理を行います。よって以下のような式が成り立ちます。

よって最悪計算量はだということが導けます。

さいごに

最近やたらアルゴリズム関連の記事が多くなってしまっているのは、実はこれ関係のテストがあるからだったりします。

もしかしたらこういった基礎的なものを複数投稿するかもしれませんが、生暖かい目でみていただけると幸いです。

ではまた。