개념
정렬된 부분에 새로운 원소를 적절한 위치에 삽입하는 정렬
카드를 정렬하듯이, 하나씩 뽑아서 올바른 위치에 끼워 넣음
시간복잡도
| 케이스 | 시간복잡도 |
|---|---|
| 최선 | O(n) |
| 평균 | O(n²) |
| 최악 | O(n²) |
| 공간복잡도 | O(1) |
특징
장점
- 거의 정렬된 경우 빠름: 최선 O(n)
- 안정 정렬: 같은 값의 순서 유지
- 제자리 정렬: 추가 메모리 불필요
- 온라인 정렬: 데이터가 들어오는 대로 정렬 가능
단점
- 평균적으로 느림: O(n²) 시간복잡도
- 역순 정렬 시 최악: O(n²) 성능
구현 방법
기본 구현
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i] # 삽입할 값
j = i - 1
# key보다 큰 요소들을 한 칸씩 뒤로 이동
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
# key를 적절한 위치에 삽입
arr[j + 1] = key
return arr
# 테스트
print(insertion_sort([64, 25, 12, 22, 11]))
# [11, 12, 22, 25, 64]내림차순 구현
def insertion_sort_desc(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
# key보다 작은 요소들을 한 칸씩 뒤로 이동
while j >= 0 and arr[j] < key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# 테스트
print(insertion_sort_desc([64, 25, 12, 22, 11]))
# [64, 25, 22, 12, 11]이진 삽입 정렬 (Binary Insertion Sort)
def binary_search_position(arr, key, start, end):
"""이진 탐색으로 삽입 위치 찾기"""
while start < end:
mid = (start + end) // 2
if arr[mid] > key:
end = mid
else:
start = mid + 1
return start
def binary_insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
# 이진 탐색으로 삽입 위치 찾기
pos = binary_search_position(arr, key, 0, i)
# 요소들을 뒤로 이동
arr = arr[:pos] + [key] + arr[pos:i] + arr[i+1:]
return arr
# 테스트
print(binary_insertion_sort([64, 25, 12, 22, 11]))
# [11, 12, 22, 25, 64]
# 시간복잡도: O(n²) - 비교는 O(n log n)이지만 이동은 여전히 O(n²)동작 과정
초기: [64, 25, 12, 22, 11]
[정렬됨 | 미정렬]
1회전: key=25
[64 | 25, 12, 22, 11]
[25, 64 | 12, 22, 11] ← 64를 뒤로, 25 삽입
2회전: key=12
[25, 64 | 12, 22, 11]
[12, 25, 64 | 22, 11] ← 64, 25를 뒤로, 12 삽입
3회전: key=22
[12, 25, 64 | 22, 11]
[12, 22, 25, 64 | 11] ← 64, 25를 뒤로, 22 삽입
4회전: key=11
[12, 22, 25, 64 | 11]
[11, 12, 22, 25, 64] ← 모두 뒤로, 11 삽입
완료: [11, 12, 22, 25, 64]
템플릿
def insertion_sort_template(arr):
n = len(arr)
# i: 현재 삽입할 요소의 인덱스 (1부터 시작)
for i in range(1, n):
key = arr[i] # 삽입할 값
j = i - 1 # 정렬된 부분의 마지막 인덱스
# 정렬된 부분에서 key가 들어갈 위치 찾기
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # 큰 값들을 뒤로 이동
j -= 1
# key를 찾은 위치에 삽입
arr[j + 1] = key
return arr핵심 요약
| 개념 | 설명 |
|---|---|
| 원리 | 정렬된 부분에 하나씩 삽입 |
| 시간복잡도 | O(n²) - 최선 O(n) |
| 공간복잡도 | O(1) |
| 안정성 | 안정 정렬 |
| 특징 | 거의 정렬된 경우 매우 빠름 |
다른 정렬과 비교
| 정렬 | 시간복잡도 (평균) | 최선 | 공간복잡도 | 안정성 |
|---|---|---|---|---|
| 삽입 정렬 | O(n²) | O(n) | O(1) | 안정 |
| 선택 정렬 | O(n²) | O(n²) | O(1) | 불안정 |
| 버블 정렬 | O(n²) | O(n) | O(1) | 안정 |
| 병합 정렬 | O(n log n) | O(n log n) | O(n) | 안정 |
| 퀵 정렬 | O(n log n) | O(n log n) | O(log n) | 불안정 |
주의사항
1. 인덱스 범위 주의
# j >= 0 조건 반드시 먼저 체크
while j >= 0 and arr[j] > key: # 올바른 순서
arr[j + 1] = arr[j]
j -= 1
# 잘못된 순서 (IndexError 발생 가능)
# while arr[j] > key and j >= 0: # 위험!2. 거의 정렬된 경우 최적
# 이미 정렬된 경우: O(n)
arr = [1, 2, 3, 4, 5]
# 각 요소마다 1번만 비교
# 역순 정렬된 경우: O(n²)
arr = [5, 4, 3, 2, 1]
# 최악의 경우3. 작은 데이터에 효율적
# n < 50 정도일 때
# 퀵 정렬, 병합 정렬보다 빠를 수 있음
# (오버헤드가 적기 때문)
# Python의 Timsort도 작은 부분은 삽입 정렬 사용자주 나오는 문제 유형
1. 거의 정렬된 배열 정렬
문제: K개 떨어진 요소들끼리만 교환 가능한 배열 정렬
import heapq
def sort_k_sorted_array(arr, k):
"""각 요소가 최대 k칸 떨어진 위치에 있는 배열 정렬"""
n = len(arr)
result = []
# 최소 힙 생성 (k+1개 요소)
heap = arr[:k + 1]
heapq.heapify(heap)
for i in range(k + 1, n):
result.append(heapq.heappop(heap))
heapq.heappush(heap, arr[i])
# 힙에 남은 요소들 추가
while heap:
result.append(heapq.heappop(heap))
return result
# 테스트
print(sort_k_sorted_array([3, 2, 1, 5, 4, 7, 6, 5], 3))
# [1, 2, 3, 4, 5, 5, 6, 7]
# 시간복잡도: O(n log k)핵심: 힙을 사용하여 K개씩만 정렬
2. 삽입 정렬로 정렬 중 특정 위치 추적
문제: 삽입 정렬 과정에서 특정 값의 위치 변화 추적
def insertion_sort_track_position(arr, target):
n = len(arr)
positions = []
# target의 초기 인덱스 찾기
target_idx = arr.index(target)
for i in range(1, n):
key = arr[i]
j = i - 1
# 현재 삽입하는 요소가 target인지 확인
is_target = (i == target_idx)
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
# target이 뒤로 밀리는 경우
if j == target_idx:
target_idx = j + 1
j -= 1
arr[j + 1] = key
# 삽입된 요소가 target인 경우
if is_target:
target_idx = j + 1
positions.append(target_idx)
return arr, positions
# 테스트
result, positions = insertion_sort_track_position([5, 3, 8, 4, 2], 8)
print(f"정렬 결과: {result}")
print(f"8의 위치 변화: {positions}")핵심: 삽입 과정에서 인덱스 추적
3. 삽입 정렬의 교환 횟수 세기
문제: 삽입 정렬 시 이동 횟수(=역순 쌍의 개수) 계산
def insertion_sort_count_moves(arr):
n = len(arr)
move_count = 0
for i in range(1, n):
key = arr[i]
j = i - 1
# key보다 큰 요소들을 이동
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
move_count += 1 # 이동 횟수 증가
j -= 1
arr[j + 1] = key
return arr, move_count
# 테스트
result, moves = insertion_sort_count_moves([5, 3, 8, 4, 2])
print(f"정렬 결과: {result}")
print(f"이동 횟수: {moves}") # 7
# 이동 횟수 = 배열의 역순 쌍(inversion) 개수핵심: 이동 횟수는 역순 쌍의 개수와 동일
4. 연결 리스트 삽입 정렬
문제: 연결 리스트를 삽입 정렬로 정렬
class Node:
def __init__(self, data):
self.data = data
self.next = None
def insertion_sort_list(head):
if not head or not head.next:
return head
# 더미 노드 생성
dummy = Node(0)
current = head
while current:
# 다음 노드 저장
next_node = current.next
# 삽입 위치 찾기
prev = dummy
while prev.next and prev.next.data < current.data:
prev = prev.next
# 현재 노드 삽입
current.next = prev.next
prev.next = current
# 다음 노드로 이동
current = next_node
return dummy.next
# 테스트
def create_list(arr):
dummy = Node(0)
current = dummy
for val in arr:
current.next = Node(val)
current = current.next
return dummy.next
def print_list(head):
values = []
while head:
values.append(head.data)
head = head.next
print(values)
head = create_list([4, 2, 1, 3])
sorted_head = insertion_sort_list(head)
print_list(sorted_head) # [1, 2, 3, 4]
# 시간복잡도: O(n²)
# 공간복잡도: O(1)핵심: 더미 노드를 사용하여 삽입 위치 탐색
추천 연습 문제
기초
중급
삽입 정렬이 실전에서 쓰이는 이유
1. Timsort에서 활용
# Python의 기본 정렬 (sort, sorted)
# 작은 부분 배열(< 64)은 삽입 정렬 사용
arr.sort() # 내부적으로 Timsort (병합 + 삽입)2. 퀵 정렬 최적화
# 재귀 깊이가 깊어지면 삽입 정렬로 전환
def quick_sort_hybrid(arr, low, high):
if high - low < 10: # 작은 부분은 삽입 정렬
insertion_sort(arr[low:high+1])
else:
# 퀵 정렬 수행
pass3. 온라인 알고리즘
# 데이터가 들어오는 대로 정렬
sorted_arr = []
for data in stream:
# 삽입 정렬로 즉시 정렬된 상태 유지
insert_sorted(sorted_arr, data)언제 사용할까?
사용 가능
- 거의 정렬된 데이터: O(n)에 가까운 성능
- 작은 데이터: n < 50 정도
- 온라인 정렬: 데이터가 계속 들어올 때
- 안정 정렬 필요: 같은 값의 순서 유지
사용 불가
- 역순 또는 무작위 데이터: O(n²)
- 대용량 데이터: 병합 정렬, 퀵 정렬 사용
- 최악의 경우 보장: 병합 정렬 사용
결론: 작고 거의 정렬된 데이터에 최적, 실전에서도 많이 활용됨!