Python 알고리즘

Python의 삽입 정렬(insertion sort)

이 레슨에서는 각 요소를 이미 정렬된 부분의 알맞은 자리에 끼워 넣는 삽입 정렬을 구현합니다.

  • 중급
  • 2분 분량
  • 실행 가능한 예제 1개

소개

어떤 문제를 해결하나요

데이터는 거의 정렬된 상태로 오거나 하나씩 들어오는 경우가 많습니다. 예를 들어 정렬된 점수 목록에 새 점수가 하나 추가됩니다. 이때 전체를 다시 정렬하는 것은 낭비입니다. 삽입 정렬(insertion sort)은 이런 경우에 아주 잘 맞습니다. 많은 사람이 손에 든 카드를 정리할 때 쓰는 방법이기도 합니다.

일상 속 비유

삽입 정렬은 손에 든 카드를 정리하는 방법과 같습니다. 카드를 한 장씩 집어서, 그보다 큰 카드들을 지나 왼쪽으로 옮기다가 제자리에 끼워 넣습니다. 그 카드의 왼쪽에 있는 카드들은 언제나 정렬되어 있습니다.

카드 정리에서 코드로
current = result[index]🃏 다음 카드 집기
result[position] > current👈 왼쪽 카드가 더 큰가요?
result[position + 1] = result[position]➡️ 더 큰 카드를 오른쪽으로 한 칸 밀기
result[position + 1] = current📥 생긴 빈칸에 카드 넣기
왼쪽 부분은 언제나 정렬되어 있고, 새 항목을 그 안에 끼워 넣습니다.
한 문장으로

삽입 정렬은 정렬된 부분을 항목 하나씩 늘려 갑니다. 더 큰 항목들을 오른쪽으로 밀고, 그렇게 생긴 빈칸에 지금 항목을 넣습니다. 최악의 경우 O(n²)이지만, 거의 정렬된 데이터에서는 O(n)에 가깝습니다.

핵심 포인트

  1. for index in range(1, len(result)):은 두 번째 항목부터 시작합니다. 항목이 하나뿐이면 이미 정렬된 것이기 때문입니다.
  2. current는 더 큰 값들이 옮겨지는 동안, 끼워 넣을 값을 보관합니다.
  3. while position >= 0 and result[position] > current:는 더 큰 값을 하나씩 오른쪽으로 한 칸 밉니다.
  4. result[position + 1] = current는 그렇게 생긴 빈칸에 값을 넣습니다.

언제 사용하나요?

  • 작은 리스트나 거의 정렬된 리스트.
  • 새 항목이 들어올 때마다 리스트를 정렬된 상태로 유지할 때.
  • 더 빠른 정렬 알고리즘의 마지막 단계. 이런 알고리즘은 조각이 작아지면 삽입 정렬로 바꿔서 정렬합니다.

필요 없는 경우

  • 순서가 뒤죽박죽인 큰 리스트: 값을 미는 작업이 느려지므로 sorted()를 씁니다.
  • 정렬된 큰 리스트에 값을 자주 넣는 경우: bisect.insort는 넣을 위치를 이진 탐색으로 찾습니다.

Python의 삽입 정렬(insertion sort) 시각화

O(n²)

재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.

예제 코드

코드 실행 →
main.py
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 컴파일러에서 실행하세요.

연습 문제

아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.

  1. 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
  2. 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
  3. 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
Python 컴파일러에서 실행 →

자주 하는 실수

반복문 안에서 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 리뷰를 받을 수 있습니다.

모든 챌린지