이 글에서는 아래 문제에 대한 해결 방법을 알아보겠습니다.
문제 정의 − 하나의 배열이 주어졌을 때, 반복(iteration) 기반의 병합 정렬 개념을 활용하여 해당 배열을 정렬해야 합니다.
반복적 병합 정렬이란?
병합 정렬(Merge Sort)은 일반적으로 재귀 호출을 사용해 배열을 분할한 뒤 다시 합치는 방식으로 구현됩니다. 반면 반복적 병합 정렬(Iterative Merge Sort)은 재귀 대신 반복문만을 사용하기 때문에 스택 오버플로우를 걱정할 필요 없이 안정적으로 동작한다는 장점이 있습니다.
동작 방식은 다음과 같습니다.
- 처음에는 크기가 1인 하위 배열부터 시작합니다.
- 인접한 두 하위 배열을 병합하여 크기가 두 배인 정렬된 하위 배열을 만듭니다.
- 하위 배열의 크기를 두 배씩 늘려가며 위 과정을 배열 전체가 정렬될 때까지 반복합니다.
구현 예제
# 반복적 방식
def mergeSort(a):
current_size = 1
# 하위 배열 순회
while current_size < len(a) - 1:
left = 0
# 정렬 대상 하위 배열 처리
while left < len(a) - 1:
# 중간(mid) 값 계산
mid = left + current_size - 1
# 오른쪽 경계 계산
right = ((2 * current_size + left - 1, len(a) - 1)[2 * current_size + left - 1 > len(a) - 1])
# 병합 수행
merge(a, left, mid, right)
left = left + current_size * 2
# 하위 배열 크기를 두 배로 증가
current_size = 2 * current_size
# 병합 함수
def merge(a, l, m, r):
n1 = m - l + 1
n2 = r - m
L = [0] * n1
R = [0] * n2
for i in range(0, n1):
L[i] = a[l + i]
for i in range(0, n2):
R[i] = a[m + i + 1]
i, j, k = 0, 0, l
while i < n1 and j < n2:
if L[i] > R[j]:
a[k] = R[j]
j += 1
else:
a[k] = L[i]
i += 1
k += 1
while i < n1:
a[k] = L[i]
i += 1
k += 1
while j < n2:
a[k] = R[j]
j += 1
k += 1
# 드라이버 코드
a = [2, 5, 3, 8, 6, 5, 4, 7]
mergeSort(a)
print("Sorted array is:")
for i in range(len(a)):
print(a[i], end=" ")
출력 결과
Sorted array is 2 3 4 5 5 6 7 8
코드 분석
모든 변수는 지역 범위(local scope) 내에서 선언되며, 각 변수의 참조 관계는 위 그림에서 확인할 수 있습니다.
- mergeSort() : 하위 배열의 크기를 1부터 시작해 두 배씩 늘려가며, 배열 전체가 하나의 정렬된 배열이 될 때까지 인접한 하위 배열들을 순차적으로 병합합니다.
- merge() : 왼쪽 부분 배열(L)과 오른쪽 부분 배열(R)의 요소를 하나씩 비교하여, 작은 값부터 원본 배열에 차례대로 채워 넣습니다. 한쪽 배열이 모두 소진되면 남은 요소들을 그대로 이어 붙입니다.
이 알고리즘의 시간 복잡도는 O(n log n)이며, 병합 과정에서 보조 배열을 사용하므로 공간 복잡도는 O(n)입니다.
결론
이 글에서는 재귀 호출 없이 반복문만으로 구현하는 파이썬 반복적 병합 정렬 프로그램을 작성하는 방법을 학습했습니다. 재귀 버전과 달리 호출 스택의 깊이 제한에 영향을 받지 않으므로, 대용량 데이터를 정렬해야 하는 상황에서 특히 유용하게 활용할 수 있습니다.