[C언어] 삽입 정렬(Insertion Sort) 쉽게 배우기 – 정렬 알고리즘 예제와 코드

🧩 C언어 삽입 정렬(Insertion Sort) 쉽게 배우기 – 정렬 알고리즘 예제와 코드

지난 글에서는 버블 정렬과 선택 정렬을 배워보았습니다.
이번 글에서는 또 다른 기초 정렬 알고리즘인 삽입 정렬(Insertion Sort)을 설명드리겠습니다.
카드 놀이에서 손에 든 카드를 정렬된 순서에 맞게 끼워 넣는 방식으로 이해하시면 훨씬 쉽게 다가올 것입니다.

---

✅ 1. 삽입 정렬이란?

• 배열의 왼쪽 부분을 정렬된 영역으로 유지합니다.
• 오른쪽에서 새로운 원소를 하나 꺼내어, 정렬된 영역의 올바른 위치에 삽입합니다.
• 작은 데이터나 거의 정렬된 배열에 대해서는 매우 효율적으로 동작합니다.

---

✅ 2. 알고리즘 동작 과정

1. i = 1부터 시작합니다. (arr[0]은 이미 정렬된 구간으로 간주합니다.)
2. key = arr[i] 값을 저장합니다.
3. 왼쪽으로 이동하면서 arr[j] > key이면 한 칸씩 뒤로 밀어냅니다.
4. 멈춘 위치에 key를 삽입합니다.

---

✅ 3. C언어 코드 예제 (오름차순)

#include <stdio.h>

int main() {
    int arr[] = {5, 3, 4, 1, 2};
    int n = sizeof(arr)/sizeof(arr[0]);

    for (int i = 1; i < n; 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;
    }

    printf("정렬 결과: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

실행 결과: 정렬 결과: 1 2 3 4 5

---

⚡ 4. 내림차순 변형

비교 연산자를 <로 바꾸면 내림차순 정렬이 됩니다.

while (j >= 0 && arr[j] < key) {
    arr[j + 1] = arr[j];
    j--;
}
arr[j + 1] = key;

---

🧠 5. 시간 복잡도 및 특징

• 최선의 경우: O(n) (이미 정렬된 경우)
• 평균 및 최악의 경우: O(n²)
• 공간 복잡도: O(1) (제자리 정렬)
• 안정 정렬: 동일한 값의 순서가 바뀌지 않습니다.
• 거의 정렬된 데이터에 강력하며, 실무에서도 보조 알고리즘으로 자주 활용됩니다.

---

🧩 6. 단계별 시뮬레이션

입력: {5, 3, 4, 1, 2}

1. i=1, key=3 → {3, 5, 4, 1, 2}
2. i=2, key=4 → {3, 4, 5, 1, 2}
3. i=3, key=1 → {1, 3, 4, 5, 2}
4. i=4, key=2 → {1, 2, 3, 4, 5}

---

❗ 7. 자주 하는 실수

• j 범위 확인 누락 (j >= 0 조건 필수)
• arr[j + 1] = key; 삽입 위치를 잘못 지정
• key 값을 별도 변수에 저장하지 않아 덮어씌워지는 문제

---

🔁 8. 버블·선택 정렬과 비교

알고리즘	최선	평균/최악	교환 횟수	안정성	특징
버블 정렬	O(n)	O(n²)	많음	안정	구현 쉬움
선택 정렬	O(n²)	O(n²)	적음	불안정	교환 적지만 항상 n²
삽입 정렬	O(n)	O(n²)	중간	안정	거의 정렬된 데이터에 강함

---

📝 9. 연습 문제

1. 배열 {9, 1, 6, 3, 7}을 삽입 정렬로 정렬해 보세요.
2. 내림차순 삽입 정렬을 직접 구현해 보세요.
3. void insertion_sort_desc(int* arr, int n) 형태로 함수화해 보세요.

---

🔗 10. 내부 링크 시리즈

• [Day 8] 버블 정렬
• [Day 9] 선택 정렬
• [Day 10] 삽입 정렬
• [Day 11] 퀵 정렬 (예고)

---

📌 다음 강의 예고

다음 글에서는 퀵 정렬(Quick Sort)을 다룹니다.
분할 정복과 재귀 함수를 활용하여 효율적으로 정렬하는 방법을 배워보겠습니다.

👉 다음 글: C언어 퀵 정렬(Quick Sort)

---

이 글이 도움이 되셨다면 댓글과 공감 부탁드립니다.
더 많은 학습 글은 👉 Coding Life 100 Hacks 에서 확인하실 수 있습니다 😊