C# 삽입 정렬(Insertion Sort) 알고리즘 완벽 가이드

삽입 정렬(Insertion Sort)은 배열의 요소를 하나씩 가져와서 이미 정렬된 부분 중 올바른 위치에 삽입하는 방식으로 동작하는 정렬 알고리즘입니다. 마치 카드 게임에서 손에 든 카드를 순서대로 정리하듯이, 각 요소를 적절한 자리에 끼워 넣는 과정을 배열 전체가 정렬될 때까지 반복합니다.

삽입 정렬은 구현이 간단하고 데이터 양이 적거나 거의 정렬된 상태의 배열에서 뛰어난 성능을 보이기 때문에 실무에서도 유용하게 활용됩니다.

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

코드 상세 설명

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 반복문을 통해 이루어집니다. 외부 for 반복문이 한 번 실행될 때마다 현재 요소(val)를 가져온 뒤, 내부 반복문에서 앞쪽에 있는 요소들과 차례로 비교하여 자신보다 큰 값이 있으면 그 값을 한 칸씩 뒤로 밀고, 적절한 위치를 찾으면 현재 값을 삽입합니다. 이 과정은 배열 전체가 정렬될 때까지 반복됩니다.

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 변수는 현재 요소가 자신의 올바른 위치를 찾았음을 나타내는 역할을 합니다. 비교 대상인 앞의 요소가 현재 값보다 작거나 같으면 더 이상 이동할 필요가 없으므로 flag를 1로 설정해 내부 반복문을 종료합니다.

3. 정렬된 배열 출력

마지막으로 정렬이 완료된 배열을 for 반복문을 사용하여 화면에 출력합니다.

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

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 다음과 같습니다.

최선의 경우(Best Case): O(n) — 배열이 이미 정렬되어 있는 경우, 각 요소를 한 번씩만 비교하면 됩니다.
평균 및 최악의 경우(Average/Worst Case): O(n²) — 배열이 역순으로 정렬되어 있는 경우 각 요소를 모든 앞 요소와 비교해야 합니다.

공간 복잡도는 제자리(in-place) 정렬 방식이므로 O(1)로 매우 효율적입니다. 따라서 데이터 크기가 작거나 대부분 정렬된 데이터를 다룰 때 삽입 정렬은 간단하면서도 효과적인 선택이 될 수 있습니다.