이 글에서는 파이썬을 이용해 재귀 삽입 정렬(Recursive Insertion Sort)을 구현하는 방법을 예제 코드와 함께 자세히 살펴보겠습니다.
문제 정의
하나의 배열이 주어졌을 때, 반복문 대신 재귀 호출의 개념을 활용하여 해당 배열을 오름차순으로 정렬하는 것이 목표입니다.
삽입 정렬의 기본 원리
삽입 정렬은 카드 게임에서 손에 든 카드를 정리하는 것과 유사한 방식으로 동작합니다. 각 요소를 차례대로 확인하면서, 이미 정렬된 앞부분 배열 안에서 자신의 올바른 위치를 찾아 직접 삽입하는 알고리즘입니다.
일반적인 삽입 정렬은 for문과 while문 같은 반복문을 사용하지만, 재귀 버전에서는 반복문 역할을 재귀 함수 호출이 대신 수행합니다.
재귀적 접근 방식
재귀 삽입 정렬의 핵심 아이디어는 다음과 같습니다.
- 먼저 앞의 n-1개 원소를 재귀적으로 정렬합니다.
- 그다음 마지막 원소(n번째 원소)를 이미 정렬된 앞부분의 적절한 위치에 삽입합니다.
구현 예제
# 재귀 방식의 삽입 정렬
def insertionSortRecursive(arr, n):
# 기저 사례(base case): 원소가 1개 이하면 이미 정렬된 상태
if n <= 1:
return
# 앞의 n-1개 원소를 먼저 재귀적으로 정렬
insertionSortRecursive(arr, n - 1)
last = arr[n - 1]
j = n - 2
# 마지막 원소보다 큰 원소들을 한 칸씩 뒤로 이동
while (j >= 0 and arr[j] > last):
arr[j + 1] = arr[j]
j = j - 1
arr[j + 1] = last
# 메인 실행부
arr = [1, 5, 3, 4, 8, 6, 3, 4, 5]
n = len(arr)
insertionSortRecursive(arr, n)
print("정렬된 배열:")
for i in range(n):
print(arr[i], end=" ")실행 결과
정렬된 배열: 1 3 3 4 4 5 5 6 8
코드 동작 과정 상세 분석
위 코드의 실행 흐름을 단계별로 살펴보면 다음과 같습니다.
- 기저 사례 처리: n이 1 이하가 되면 더 이상 정렬할 원소가 없으므로 재귀 호출을 종료합니다. 이는 무한 재귀를 방지하는 핵심 장치입니다.
- 재귀 호출: insertionSortRecursive(arr, n-1)을 호출하여 첫 번째 원소부터 n-1번째 원소까지를 먼저 정렬합니다.
- 원소 삽입: 마지막 원소(last)를 임시 변수에 저장한 뒤, 앞쪽 원소들 중 last보다 큰 값들을 한 칸씩 뒤로 밀어내고, 빈자리에 last를 삽입합니다.
모든 변수는 지역 범위(local scope) 내에서 선언되며, 각 재귀 호출마다 독립적인 n과 j 값을 가지게 됩니다.
시간 및 공간 복잡도
- 최악/평균 시간 복잡도: O(n²) — 배열이 역순으로 정렬된 경우 모든 원소를 비교하고 이동해야 합니다.
- 최선 시간 복잡도: O(n) — 배열이 이미 정렬되어 있는 경우 삽입 연산 없이 재귀 호출만 진행됩니다.
- 공간 복잡도: O(n) — 재귀 호출 스택이 깊이 n만큼 쌓이기 때문에 일반 삽입 정렬(O(1))보다 추가 메모리를 사용합니다.
결론
이 글에서는 파이썬으로 재귀 삽입 정렬을 구현하는 방법을 배웠습니다. 반복문 기반 구현에 비해 재귀 방식은 코드가 간결하고 알고리즘의 분할 정복 사고방식을 이해하는 데 도움이 되지만, 재귀 스택으로 인한 메모리 오버헤드가 있다는 점을 기억해 두시기 바랍니다.