C＃での挿入ソート

挿入ソートは、一度に要素を取得し、それを配列内の正しい位置に挿入するソートアルゴリズムです。このプロセスは、配列がソートされるまで続けられます。

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

それでは、上記のプログラムを理解しましょう。

最初に配列が初期化され、その値が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] + " ");
}

ネストされたforループは、実際の並べ替えプロセスに使用されます。外側のforループの各パスで、現在の要素が配列内の正しい位置に挿入されます。このプロセスは、配列がソートされるまで続きます。これは、次のコードスニペットで確認できます。

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] + " ");
}