Python으로 배우는 삽입 정렬(Insertion Sort): 개념부터 구현까지

이 글에서는 Python 3.x 환경에서 삽입 정렬(Insertion Sort)을 구현하는 방법을 단계별로 살펴봅니다. 삽입 정렬은 손안의 카드를 정렬하듯이 각 요소를 이미 정렬된 부분 배열의 올바른 위치에 '삽입'하는 직관적인 알고리즘입니다.

알고리즘 동작 원리

반복할 때마다 정렬된 부분 배열을 하나씩 확장해가며 입력 요소들을 순회합니다.
현재 처리 중인 요소(key)를 정렬된 부분 배열에서 가장 큰 값과 비교합니다.
현재 요소가 더 크다면 그 자리에 두고 다음 요소로 넘어갑니다. 반대로 더 작다면, 정렬된 부분 배열 내에서 자신의 올바른 위치를 찾아 그곳으로 이동시킵니다.
이 과정은 정렬된 부분 배열에서 현재 요소보다 큰 값들을 모두 한 칸씩 오른쪽으로 밀어내는 방식으로 수행됩니다.

구현 예제

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # arr[0..i-1] 범위에서 key보다 큰 요소들을
        # 한 칸씩 뒤로 밀어냅니다.
        j = i-1
        while j >=0 and key < arr[j] :
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

# 메인 부분
arr = ['t','u','t','o','r','i','a','l']
insertionSort(arr)
print ("정렬된 배열:")
for i in range(len(arr)):
    print (arr[i])

실행 결과

정렬된 배열:
a
i
l
o
r
t
t
u

복잡도 분석

시간 복잡도: O(n²) — 최악의 경우(역순으로 정렬된 입력) 각 요소마다 앞선 모든 요소와 비교해야 하므로 이중 반복이 발생합니다. 다만 이미 정렬된 입력에서는 O(n)으로 매우 빠르게 동작합니다.
보조 공간(공간 복잡도): O(1) — 추가적인 배열 없이 제자리(in-place)에서 정렬이 이루어지므로 메모리 사용량이 일정합니다.

삽입 정렬은 구현이 간단하고 안정 정렬(stable sort)이라는 장점이 있어, 데이터 크기가 작거나 거의 정렬된 상태일 때 특히 효율적입니다. 실제로 퀵 정렬 같은 고급 알고리즘에서도 작은 구간을 정렬할 때 보조적으로 사용되기도 합니다.

마무리

이번 글에서는 삽입 정렬의 기본 원리와 Python 3.x에서의 구현 방법, 그리고 시간·공간 복잡도까지 함께 살펴보았습니다. 작은 데이터셋이나 거의 정렬된 데이터를 다룰 때 유용한 삽입 정렬을 직접 구현해 보며 정렬 알고리즘의 기초를 탄탄히 다져보시기 바랍니다.