C#で学ぶ挿入ソート（Insertion Sort）の基本と実装方法

挿入ソートとは

挿入ソート（Insertion Sort）は、配列から要素を1つずつ取り出し、その要素を配列内の正しい位置に挿入していくソートアルゴリズムです。この処理を繰り返すことで、最終的に配列全体が昇順に並べ替えられます。トランプの手札を整理するイメージに近く、直感的に理解しやすいのが特徴です。

以下は、C#で挿入ソートを実装したサンプルプログラムです。

サンプルコード

using System;
namespace InsertionSortDemo {
    class Example {
        static void Main(string[] args) {
            int[] arr = new int[10] { 23, 9, 85, 12, 99, 34, 60, 15, 100, 1 };
            int n = 10, i, j, val, flag;
            Console.WriteLine("Insertion Sort");
            Console.Write("Initial array is: ");
            for (i = 0; i < n; i++) {
                Console.Write(arr[i] + " ");
            }
            for (i = 1; i < n; i++) {
                val = arr[i];
                flag = 0;
                for (j = i - 1; j >= 0 && flag != 1; ) {
                    if (val < arr[j]) {
                        arr[j + 1] = arr[j];
                        j--;
                        arr[j + 1] = val;
                    }
                    else flag = 1;
                }
            }
            Console.Write("\nSorted Array is: ");
            for (i = 0; i < n; i++) {
                Console.Write(arr[i] + " ");
            }
        }
    }
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

Insertion Sort
Initial array is: 23 9 85 12 99 34 60 15 100 1
Sorted Array is: 1 9 12 15 23 34 60 85 99 100

プログラムの解説

ここからは、上記のプログラムがどのように動作しているのかを順番に見ていきましょう。

1. 配列の初期化と初期状態の表示

まず、配列を初期化し、forループを使ってその内容をコンソールに出力します。該当するコードは以下の通りです。

int[] arr = new int[10] { 23, 9, 85, 12, 99, 34, 60, 15, 100, 1 };
int n = 10, i, j, val, flag;
Console.WriteLine("Insertion Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
    Console.Write(arr[i] + " ");
}

2. ソート処理の本体

実際の並べ替え処理は、入れ子になったforループによって行われます。外側のループの各パスでは、現在注目している要素（val）を取り出し、それより前の整列済み部分の中で適切な位置へと挿入していきます。挿入すべき位置が見つかるまで、後ろの要素を1つずつずらしながら比較を続けます。この処理を全要素に対して繰り返すことで、配列全体がソートされます。

for (i = 1; i < n; i++) {
    val = arr[i];
    flag = 0;
    for (j = i - 1; j >= 0 && flag != 1; ) {
        if (val < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
            arr[j + 1] = val;
        } else flag = 1;
    }
}

変数flagは、挿入位置が確定した時点で内側のループを早期に抜けるためのフラグとして機能しています。これにより、無駄な比較を減らし、効率的な動作を実現しています。

3. ソート結果の表示

最後に、並べ替えが完了した配列をコンソールに出力します。該当するコードは以下の通りです。

Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
    Console.Write(arr[i] + " ");
}

まとめ

挿入ソートは、計算量がO(n²)とデータ数が多い場合には非効率になりますが、実装がシンプルで、ほぼ整列済みのデータに対しては高速に動作するという利点があります。アルゴリズムの基礎を学ぶうえで非常に良い題材なので、ぜひ自分でもコードを書いて動作を確認してみてください。