Insertion Sort

정의

Insertion Sort (삽입 정렬) 는 한 번에 한 원소씩 이미 정렬된 부분에 올바른 위치를 찾아 삽입 하는 정렬. 카드 정리하듯이 한 장씩 적절한 자리에 끼워넣는 동작.

O(n²) 알고리즘 중 실측 가장 빠르다. 작은 입력 (n ≤ 16) 이나 거의 정렬된 입력에서 Quick Sort 같은 O(n log n) 알고리즘보다도 빠를 수 있다. 그래서 Timsort, Introsort, Pdqsort 가 부분 정렬에 모두 Insertion Sort 를 사용한다.

전체 비교는 정렬 알고리즘 참고.

시각화

key 를 찾아 올바른 자리에 끼워넣는 과정:

flowchart LR
    Start["i=1"] --> Key["key = arr[i], j = i-1"]
    Key --> CMP{"j >= 0 AND arr[j] > key?"}
    CMP -->|"Yes"| Shift["arr[j+1] = arr[j], j--"]
    Shift --> CMP
    CMP -->|"No"| Insert["arr[j+1] = key"]
    Insert --> Inc{"i < n?"}
    Inc -->|"Yes"| Key2["i++, 다음 원소"]
    Inc -->|"No"| Done["정렬 완료"]
    Key2 --> Key

알고리즘

insertionSort(arr):
  for i = 1 to n-1:
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
      arr[j + 1] = arr[j]  // 한 칸씩 오른쪽으로 밀기
      j--
    arr[j + 1] = key       // 빈 자리에 삽입

핵심 동작

배열 앞부분이 이미 정렬된 영역, 나머지가 미처리 영역. 미처리에서 하나씩 꺼내 정렬된 영역의 올바른 위치에 삽입.

[ 정렬됨 | 미처리 ]
[ 5    | 2, 8, 1, 4 ]   초기

[ 2, 5 | 8, 1, 4 ]      2 를 5 앞에 삽입
[ 2, 5, 8 | 1, 4 ]      8 은 이미 5 보다 큼, 그 자리에
[ 1, 2, 5, 8 | 4 ]      1 을 맨 앞으로
[ 1, 2, 4, 5, 8 | ]     4 를 5 앞에 삽입

매 단계에서 정렬된 영역이 정확히 정렬 상태를 유지.

구현

#include <bits/stdc++.h>
using namespace std;
​
void insertionSort(vector<int>& arr) {
  int n = arr.size();
  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;
  }
}
​
int main() {
  vector<int> arr = {12, 11, 13, 5, 6};
  cout << "Before: ";
  for (int x : arr) cout << x << " ";
  cout << "\n";
  insertionSort(arr);
  cout << "After:  ";
  for (int x : arr) cout << x << " ";
  cout << "\n";
  // 역순 입력 (최악)
  vector<int> rev = {5, 4, 3, 2, 1};
  insertionSort(rev);
  cout << "Reversed: ";
  for (int x : rev) cout << x << " ";
  cout << "\n";
}

def insertion_sort(arr: list) -> None:
  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
​
arr = [12, 11, 13, 5, 6]
print("Before:", arr)
insertion_sort(arr)
print("After: ", arr)
​
# 거의 정렬된 입력 (최선)
near_sorted = [1, 2, 4, 3, 5, 6]
insertion_sort(near_sorted)
print("Nearly sorted:", near_sorted)

Before: 12 11 13 5 6
After:  5 6 11 12 13
Reversed: 1 2 3 4 5

복잡도

왜 O(n²) 중 가장 빠른가

1. 상수항 작음: inner loop 가 단순한 비교 + 이동 한 번
2. 캐시 친화: 인접 메모리 접근만
3. 거의 정렬된 입력에 O(n) 에 가깝게 동작
4. 분기 예측 친화적: 조건이 단순

정렬된 부분의 활용

Insertion Sort 의 최대 장점은 입력의 부분적 정렬을 직접 활용 한다는 것.

const nearSorted = [1, 2, 3, 5, 4, 6, 7, 8, 9];
// 5, 4 만 어긋남
// insertion sort: 4 를 한 칸 이동 → 1 swap, 끝
// O(n) 실측

이 성질이 Timsort (Python sorted, Java Arrays.sort) 의 기반:

1. 입력에서 자연스러운 run (정렬된 부분) 식별
2. 짧은 run 은 Insertion Sort 로 길이 맞춤
3. run 들을 Merge Sort 로 합침

하이브리드 알고리즘에서의 역할

Binary Insertion Sort

삽입 위치를 이진 탐색 으로 찾음. 비교 횟수는 O(n log n) 이지만 이동 횟수는 여전히 O(n²). 비교 비용이 비싼 경우 (예: 긴 문자열) 에 유리.

일반: O(n) 비교 × O(n) = O(n²)
이진: O(log n) 비교 × O(n) = O(n log n) 비교
       O(n) 이동 × O(n) = O(n²) 이동

총 비용은 여전히 O(n²) 지만 비교 횟수가 줄어든다.

Bubble / Selection 과의 비교

실무 활용 (의외로 자주)

Insertion Sort 자체로는 작은 입력에 한정되지만, 하이브리드 알고리즘의 부속품 으로 거의 모든 표준 라이브러리에 들어가 있다.

• Python sorted(), list.sort() → Timsort 내부
• Java Arrays.sort() (객체) → Timsort 내부
• C++ std::sort → Introsort 내부 (n ≤ 16 에서)
• Rust slice::sort_unstable → Pdqsort 내부

n=8 같은 작은 배열을 정렬할 일이 있으면 Insertion Sort 가 올바른 선택.

함정

1. “삽입” 과 “교환” 혼동

Insertion Sort 는 원소를 shift (이동) 하지 교환하지 않는다. arr[j+1] = arr[j] 로 한 칸씩 밀고, 마지막에 arr[j+1] = key 로 삽입. Bubble Sort 처럼 swap 을 반복하는 것보다 효율적 (이동 1회 vs swap 3회).

2. 인덱스 경계

j >= 0 조건을 반드시 확인. arr[j] 가 범위를 벗어나기 전에 while 루프를 종료해야 함. C++ 에서 j 가 int 가 아닌 size_t (unsigned) 이면 j >= 0 가 항상 true 가 되어 무한 루프.

3. 역순 입력이 최악

역순 배열에서 i번째 원소를 삽입하려면 최대 i번 shift. 총 n*(n-1)/2 shift = O(n^2). Bubble Sort 와 같은 최악이지만 shift 연산이 swap 보다 빠르므로 실측에서는 Bubble 보다 빠름.

4. 비교 비용이 비싼 경우

원소 비교 비용이 크면 (예: 긴 문자열, 복합 키) Binary Insertion Sort 가 유리: 이진 탐색으로 삽입 위치를 O(log i) 에 결정. 이동 횟수는 그대로 O(n^2) 이지만 비교 횟수가 O(n log n) 으로 줄어듦.

5. 안정 정렬 보장 조건

arr[j] > key (strict) 비교를 유지해야 stable. arr[j] >= key 로 바꾸면 같은 키 원소의 상대 순서가 뒤바뀜.

BOJ 연습 문제

참고

• 정렬 알고리즘
• Bubble Sort
• Selection Sort
• Merge Sort
• Quick Sort
• Knuth, TAOCP Vol. 3 §5.2.1