삽입 정렬 (Insertion Sort)

손에 든 카드를 앞쪽의 정렬된 구간에 끼워 넣듯 동작하는 삽입 정렬을 막대 애니메이션으로 확인하세요. 거의 정렬된 데이터에서 O(n)에 가깝게 빠른 이유를 직접 볼 수 있습니다.

알고리즘

배열

크기48
비교 중교환/쓰기피벗/기준읽기정렬 확정
속도50×

비교

0

교환/쓰기

0

스텝

0/1,373

읽기

0

보조 메모리

0

재귀 깊이

1/1

재생 속도를 늦추고 '한 단계'로 따라가며 의사코드 하이라이트와 막대 색을 비교해 보세요.

의사코드

for i ← 1 to n−1

key ← a[i], j ← i−1

while j ≥ 0 and a[j] > key

a[j+1] ← a[j], j ← j−1

a[j+1] ← key

시간 복잡도

최선O(n)
평균O(n²)
최악O(n²)
공간O(1)
안정O

삽입 정렬은 카드를 손에 쥐고 정리하는 방식과 같습니다. 두 번째 원소부터 하나씩 집어 들어(key), 왼쪽의 이미 정렬된 구간에서 자기보다 큰 값들을 한 칸씩 뒤로 밀고 빈자리에 끼워 넣습니다.

최악(역순)에는 O(n²)이지만, 거의 정렬된 배열에서는 각 원소가 조금만 이동하면 되어 사실상 O(n)에 가깝게 동작합니다. 이 특성 때문에 실제 라이브러리 정렬(Timsort, Introsort)도 작은 구간에서는 삽입 정렬로 전환합니다.

안정 정렬이며 추가 메모리가 O(1)이라 제자리 정렬입니다. '거의 정렬됨' 프리셋과 '역순' 프리셋의 교환/쓰기 횟수 차이를 보면 입력 상태에 따라 성능이 얼마나 달라지는지 한눈에 확인됩니다. 정렬 알고리즘 시각화에서 다른 알고리즘과 같은 배열로 비교해 보세요.

자주 묻는 질문

삽입 정렬은 언제 빠른가요?
배열이 거의 정렬되어 있거나 크기가 작을 때(보통 10~50개 이하) 가장 빠릅니다. 실제 Python의 Timsort나 많은 언어의 하이브리드 정렬이 짧은 구간에 삽입 정렬을 쓰는 이유입니다.
삽입 정렬과 버블 정렬의 차이는요?
버블은 이웃끼리 매번 교환하는 반면, 삽입은 큰 값들을 뒤로 '밀기'만 하고 마지막에 한 번 씁니다. 그래서 쓰기 횟수가 적어 같은 O(n²)라도 삽입이 보통 2배가량 빠릅니다.
삽입 정렬은 안정 정렬인가요?
네. key보다 큰 값만 뒤로 밀고 같은 값은 건너뛰지 않기 때문에 원래 순서가 유지되는 안정 정렬입니다.

다른 알고리즘 보기