Python의 삽입 정렬(insertion sort)
이 레슨에서는 각 요소를 이미 정렬된 부분의 알맞은 자리에 끼워 넣는 삽입 정렬을 구현합니다.
소개
어떤 문제를 해결하나요
데이터는 거의 정렬된 상태로 오거나 하나씩 들어오는 경우가 많습니다. 예를 들어 정렬된 점수 목록에 새 점수가 하나 추가됩니다. 이때 전체를 다시 정렬하는 것은 낭비입니다. 삽입 정렬(insertion sort)은 이런 경우에 아주 잘 맞습니다. 많은 사람이 손에 든 카드를 정리할 때 쓰는 방법이기도 합니다.
일상 속 비유
삽입 정렬은 손에 든 카드를 정리하는 방법과 같습니다. 카드를 한 장씩 집어서, 그보다 큰 카드들을 지나 왼쪽으로 옮기다가 제자리에 끼워 넣습니다. 그 카드의 왼쪽에 있는 카드들은 언제나 정렬되어 있습니다.
current = result[index]🃏 다음 카드 집기result[position] > current👈 왼쪽 카드가 더 큰가요?result[position + 1] = result[position]➡️ 더 큰 카드를 오른쪽으로 한 칸 밀기result[position + 1] = current📥 생긴 빈칸에 카드 넣기삽입 정렬은 정렬된 부분을 항목 하나씩 늘려 갑니다. 더 큰 항목들을 오른쪽으로 밀고, 그렇게 생긴 빈칸에 지금 항목을 넣습니다. 최악의 경우 O(n²)이지만, 거의 정렬된 데이터에서는 O(n)에 가깝습니다.
핵심 포인트
for index in range(1, len(result)):은 두 번째 항목부터 시작합니다. 항목이 하나뿐이면 이미 정렬된 것이기 때문입니다.current는 더 큰 값들이 옮겨지는 동안, 끼워 넣을 값을 보관합니다.while position >= 0 and result[position] > current:는 더 큰 값을 하나씩 오른쪽으로 한 칸 밉니다.result[position + 1] = current는 그렇게 생긴 빈칸에 값을 넣습니다.
언제 사용하나요?
- 작은 리스트나 거의 정렬된 리스트.
- 새 항목이 들어올 때마다 리스트를 정렬된 상태로 유지할 때.
- 더 빠른 정렬 알고리즘의 마지막 단계. 이런 알고리즘은 조각이 작아지면 삽입 정렬로 바꿔서 정렬합니다.
필요 없는 경우
- 순서가 뒤죽박죽인 큰 리스트: 값을 미는 작업이 느려지므로
sorted()를 씁니다. - 정렬된 큰 리스트에 값을 자주 넣는 경우:
bisect.insort는 넣을 위치를 이진 탐색으로 찾습니다.
Python의 삽입 정렬(insertion sort) 시각화
O(n²)재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.
예제 코드
def insertion_sort(values):
result = values.copy()
for index in range(1, len(result)):
current = result[index]
position = index - 1
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
position -= 1
result[position + 1] = current
return result
print(insertion_sort([9, 5, 1, 4, 3]))
실행 결과
[1, 3, 4, 5, 9]
코드 설명
변수 current에는 끼워 넣을 값이 들어 있습니다. while 반복문은 current보다 큰 값을 오른쪽으로 한 칸씩 밀어 자리를 만들고, 그 자리에 current를 놓습니다. 최악의 경우 복잡도는 O(n²)이지만, 거의 정렬된 데이터에서는 O(n)에 가까워집니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.
- 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
- 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
- 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
자주 하는 실수
반복문 안에서 current를 써넣기
값은 더 큰 값들을 모두 옮긴 뒤에 한 번만 넣어야 합니다.
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
result[position] = current
position -= 1
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
position -= 1
result[position + 1] = current
이 레슨을 마쳤나요?
학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
모든 챌린지