손에 든 카드를 앞쪽의 정렬된 구간에 끼워 넣듯 동작하는 삽입 정렬을 막대 애니메이션으로 확인하세요. 거의 정렬된 데이터에서 O(n)에 가깝게 빠른 이유를 직접 볼 수 있습니다.
알고리즘
배열
비교
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)이라 제자리 정렬입니다. '거의 정렬됨' 프리셋과 '역순' 프리셋의 교환/쓰기 횟수 차이를 보면 입력 상태에 따라 성능이 얼마나 달라지는지 한눈에 확인됩니다. 정렬 알고리즘 시각화에서 다른 알고리즘과 같은 배열로 비교해 보세요.