보통
Insertion Sort
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 삽입정렬(nums):2 반복 i = 1 … n-1:3 키 = nums[i]4 j = i - 15 동안 j ≥ 0 그리고 nums[j] > 키:6 nums[j+1] = nums[j] // 오른쪽으로 민다7 j = j - 18 nums[j+1] = 키 // 제자리에 삽입
변수
- i
- 1
- 키
- 4
- j
- 0
1 / 19nums[1] = 4 을(를) 왼쪽 정렬 구간에 끼울 차례입니다.
새 값을 왼쪽의 이미 정렬된 구간에서 제자리를 찾아 밀어 넣는다(카드 정렬).
왜 헷갈리는가
버블 정렬과 함께 O(n²)라 실무 대량 정렬엔 안 쓴다. 그러나 '거의 정렬된 데이터'에선 O(n)에 가깝고 안정·제자리라, 실제 정렬 라이브러리가 작은 구간에서 이걸 쓴다.
핵심 아이디어
왼쪽 구간은 항상 정렬 상태를 유지한다. 다음 값을 '키'로 뽑아, 키보다 큰 값들을 오른쪽으로 밀어 자리를 만들고 그 사이에 끼워 넣는다.
복잡도
최악·평균 O(n²), 거의 정렬된 데이터는 O(n)·공간 O(1)·안정 정렬. 비교보다 이동(shift)이 비용.
실무에서 어디에 쓰나
대량 정렬은 내장 함수를 쓰되, 삽입 정렬은 '작고 거의 정렬된' 국소에서 실전 성능을 낸다.
- 하이브리드 정렬: Timsort·introsort가 작은 부분배열에서 삽입 정렬로 전환
- 온라인 정렬: 스트리밍으로 들어오는 값을 정렬 상태 유지하며 삽입
- 거의 정렬된 데이터: 로그·시계열의 소규모 지연 도착 정리
- 삽입 위치 탐색이 곧 정렬 유지 자료구조(정렬 리스트)의 기본 동작
흔한 실수
안정성 유지 위해 '크거나 같음'이 아니라 '큼(>)'으로 밀기. 이동 비용을 비교 비용으로 오해.
기억할 것
- 작고 거의 정렬된 데이터에 강하다.
- 안정·제자리 정렬.
- 하이브리드 정렬의 작은-구간 담당.
- 온라인 삽입에 적합.