삽입 정렬(Insertion Sort) 원리: 손안의 카드를 정리하는 것처럼 배우기

포커나 훌라 같은 카드 게임을 할 때, 바닥에서 카드를 한 장씩 집어 들어 손에 쥐고 있는 카드들 사이의 '올바른 위치'에 끼워 넣으며 정리해 본 경험이 있으실 겁니다. 새로운 카드를 뽑았을 때, 이미 정렬된 내 손안의 카드들을 뒤에서부터 훑어보며 자기보다 큰 카드들은 뒤로 밀어내고 제자리를 찾아 쏙 들어가는 이 우아한 과정이 바로 컴퓨터 과학의 '삽입 정렬(Insertion Sort)'입니다. 앞서 배운 선택 정렬과 똑같은 O(N^2) 알고리즘으로 분류되지만, 데이터의 상태에 따라 엄청난 잠재력을 폭발시키는 삽입 정렬만의 숨겨진 무기를 파헤쳐 보겠습니다.

1. 정렬된 구역과 미정렬 구역의 분리

삽입 정렬은 배열을 '이미 정렬된 앞부분'과 '아직 정렬되지 않은 뒷부분'으로 나누어 생각합니다. 첫 번째 원소는 그 자체로 이미 정렬되어 있다고 가정하고, 두 번째 원소부터 타겟으로 삼아 앞쪽의 정렬된 구역 어디에 '삽입'될지 결정합니다.

1-1. 뒤에서부터 앞으로 찔러넣기

배열 [5, 3, 4, 1, 2]가 있습니다.

1. 타겟 3: 앞의 5와 비교합니다. 3이 더 작으므로 5를 뒤로 한 칸 밀어내고 빈자리에 3을 넣습니다. → [3, 5, 4, 1, 2]
2. 타겟 4: 앞의 정렬된 구역 [3, 5]에 끼워 넣어야 합니다. 바로 앞의 5보다 작으므로 5를 밀어냅니다. 그다음 3과 비교했는데 4가 더 큽니다. 그렇다면 탐색을 즉시 멈추고 그 자리에 4를 넣습니다. → [3, 4, 5, 1, 2]

여기서 삽입 정렬의 가장 위대한 특징이 나옵니다. "나보다 작은 숫자를 만나는 순간, 그 앞은 볼 필요도 없이 탐색을 종료(Break)한다"는 것입니다. 이미 앞쪽은 완벽하게 정렬되어 있다는 확신이 있기 때문입니다.

2. 최선의 경우 O(N)의 경이로운 효율성

만약 배열이 [1, 2, 3, 4, 5]처럼 이미 정렬되어 있거나 거의 정렬되어 있다면 어떻게 될까요?
삽입 정렬이 2를 들고 앞의 1과 비교합니다. "어? 내가 더 크네? 그럼 난 여기 있을게." 하고 바로 다음으로 넘어갑니다. 즉, 타겟을 뽑을 때마다 단 한 번의 비교만 하고 탐색을 멈춥니다. 전체를 훑는 데 걸리는 시간은 정확히 O(N)이 됩니다.

최악의 경우(역순으로 정렬된 경우)에는 O(N^2)이 걸리지만, 데이터가 '거의 정렬된 상태(Nearly Sorted)'라면 삽입 정렬은 그 어떤 복잡하고 위대한 O(N log N) 알고리즘(퀵 정렬, 병합 정렬 등)보다도 압도적으로 빠르게 동작합니다. 이 특성 덕분에 파이썬의 기본 정렬인 팀 소트(Tim Sort) 등 현대의 고급 정렬 알고리즘들은 배열이 작게 쪼개졌을 때 마무리 작업으로 삽입 정렬을 호출하는 하이브리드 방식을 사용합니다.

[핵심 요약]
1. 삽입 정렬(Insertion Sort)은 두 번째 원소부터 시작하여, 그 앞의 정렬된 배열 부분과 비교해 자신의 올바른 위치를 찾아 '끼워 넣는' 알고리즘입니다.
2. 자신보다 작은 값을 만나는 순간 탐색을 즉시 멈추는(Break) 최적화가 들어가 있어, 데이터가 거의 정렬된 상태일수록 미친 듯이 빨라지는 특성을 가집니다.
3. 최악의 경우 O(N^2)이지만, 최선의 경우 O(N)으로 동작하여 현대의 고급 정렬 알고리즘(Tim Sort, Intro Sort)의 보조 알고리즘으로 널리 사랑받습니다.