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