[삽입 정렬] 카드를 정렬하듯, 데이터를 끼워 넣는 알고리즘

728x90

삽입 정렬(Insertion Sort) 

삽입 정렬(Insertion Sort)은 필요한 위치에 데이터를 삽입한다는 개념으로 동작하는 정렬 알고리즘입니다. 마치 카드를 손에 들고 하나씩 정렬하며 끼워 넣는 과정과 유사합니다. 간단한 구현과 직관적인 개념 덕분에 학습용으로 자주 사용되며, 실제로도 데이터가 거의 정렬되어 있는 경우 매우 효율적입니다.

 

---

1.  삽입 정렬이란?

Insertion Sort

 

삽입 정렬은 배열의 각 요소를 앞쪽 정렬된 영역에 하나씩 적절한 위치에 삽입하며 전체를 정렬해 나가는 방식입니다. 앞부분은 이미 정렬되어 있다는 가정 하에, 다음 요소를 비교하며 맞는 자리를 찾아 삽입합니다.

작동 원리

1. 두 번째 원소부터 시작해서 현재 원소를 앞쪽 정렬된 부분과 비교
2. 비교하면서 본인의 위치보다 큰 원소들은 한 칸씩 뒤로 이동
3. 빈 자리에 현재 원소를 삽입

장점

• 구현이 매우 간단
• 거의 정렬된 데이터에서는 매우 빠름
• 안정 정렬 (같은 값의 순서 보존)
• 제자리 정렬 (추가 메모리 사용 없음)

단점

• 데이터 양이 많을 경우 성능이 매우 떨어짐 (O(n²))
• 정렬 효율은 버블, 선택 정렬과 비슷

 

---

2.  예시

초기 배열 : [5, 3, 8, 1, 2]

• 3 → 5보다 작음 → 5 뒤로 → [3, 5, 8, 1, 2]
• 8 → 그대로 → [3, 5, 8, 1, 2]
• 1 → 8 → 5 → 3 뒤로 → [1, 3, 5, 8, 2]
• 2 → 8 → 5 → 3 뒤로 → [1, 2, 3, 5, 8]

 

---

3.  언어별 구현 예제

a.  Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

b.  C++

void insertionSort(std::vector<int>& arr) {
    for (int i = 1; i < arr.size(); ++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;
    }
}

c.  Java

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;
    }
}

d.  JavaScript

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let 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)
정렬 안정성	✅ 안정 정렬

• 최선의 경우 : 이미 정렬된 배열은 한 번도 이동하지 않기 때문에 O(n)
• 제자리 정렬이며, 같은 값이 있을 경우 순서를 유지 → 안정 정렬

 

---

5.  마무리

• 삽입 정렬은 데이터가 거의 정렬된 경우 가장 효율적인 단순 정렬 방식입니다.
• 정렬된 리스트에 값을 하나씩 끼워 넣듯이 동작하여 직관적이고 이해하기 쉽습니다.
• 하지만 데이터가 많거나 무작위일 경우에는 성능이 좋지 않아, 실무에서는 잘 쓰이지 않습니다.
• 면접이나 알고리즘 학습 초기 단계에서 매우 유용한 정렬 알고리즘입니다.

함께 보면 좋은 자료

외부 사이트 :

• Wikipedia - Insertion Sort

블로그 글 :

[정렬] 꼭 알아야 할 7가지 정렬 알고리즘 비교 정리

 

---

반응형