C# - 삽입 정렬 (Insertion Sort)

📥 삽입 정렬 (Insertion Sort) – 직관적이고 효율적인 정렬 방법

1. 개념

삽입 정렬은 카드 정렬과 비슷한 방식으로 작동한다.
두 번째 원소부터 시작해서, 앞쪽 정렬된 구간에 자신이 들어갈 자리를 찾아 삽입하는 방식이다.

---

2. 알고리즘 동작 방식

1. 두 번째 원소부터 시작
2. 현재 원소를 앞쪽 정렬된 구간과 비교
3. 자기보다 큰 값들을 뒤로 한 칸씩 이동
4. 알맞은 자리에 삽입

---

3. C# 예제 코드 (새로운 예제)

void InsertionSort(int[] arr)
{
    for (int i = 1; i < arr.Length; i++)
    {
        int key = arr[i];
        int j = i - 1;

        // 앞쪽 정렬된 구간에서 큰 값을 뒤로 민다
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }

        // 올바른 위치에 삽입
        arr[j + 1] = key;
    }
}

---

4. 시간/공간 복잡도

경우	시간 복잡도
최악 (역순 정렬된 배열)	O(n²)
평균	O(n²)
최선 (이미 정렬된 배열)	O(n)

 

• 공간 복잡도: O(1)

---

5. 특징

• 정렬이 거의 되어 있을수록 빠르다
• 안정 정렬 (같은 값의 순서가 유지됨)
• 코드 구조가 단순하고 직관적이어서 초보자에게 추천
• 데이터가 많을 경우에는 성능이 떨어진다

---

6. 예시

[4, 2, 5, 1]
→ 2 삽입 → [2, 4, 5, 1]
→ 5 삽입 → [2, 4, 5, 1]
→ 1 삽입 → [1, 2, 4, 5]