이 글에서는 아래의 문제 상황을 해결하는 방법을 단계별로 살펴보겠습니다.
문제 정의
문제: 하나의 배열이 주어졌을 때, 재귀 호출을 사용하지 않고 반복적(iterative) 방식의 퀵 정렬 개념을 이용해 배열을 오름차순으로 정렬해야 합니다.
퀵 정렬은 일반적으로 재귀 함수로 구현되지만, 스택(stack) 자료구조를 직접 활용하면 재귀 없이도 동일한 로직을 구현할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열을 피벗(pivot) 기준으로 분할(partition)합니다.
- 분할된 왼쪽 구간과 오른쪽 구간의 시작·끝 인덱스를 스택에 저장합니다.
- 스택이 빌 때까지 각 구간을 꺼내어 같은 과정을 반복하면 전체 배열이 정렬됩니다.
그럼 실제 구현 예제를 통해 해결 방법을 확인해 보겠습니다.
예제 코드
# 반복적 방식의 분할(partition) 함수
def partition(arr, l, h):
i = (l - 1)
x = arr[h] # 마지막 요소를 피벗으로 선택
for j in range(l, h):
if arr[j] <= x:
# 인덱스 증가 후 요소 교환
i = i + 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[h] = arr[h], arr[i + 1]
return (i + 1)
# 반복적 퀵 정렬 함수
def quickSortIterative(arr, l, h):
# 스택 생성
size = h - l + 1
stack = [0] * (size)
# 스택 포인터 초기화
top = -1
# 초기 구간(l ~ h)을 스택에 push
top = top + 1
stack[top] = l
top = top + 1
stack[top] = h
# 스택이 빌 때까지 반복
while top >= 0:
# 구간 정보 pop
h = stack[top]
top = top - 1
l = stack[top]
top = top - 1
# 피벗을 올바른 위치에 배치
p = partition(arr, l, h)
# 피벗 기준 왼쪽 구간 push
if p - 1 > l:
top = top + 1
stack[top] = l
top = top + 1
stack[top] = p - 1
# 피벗 기준 오른쪽 구간 push
if p + 1 < h:
top = top + 1
stack[top] = p + 1
top = top + 1
stack[top] = h
# 메인 실행부
arr = [2, 5, 3, 8, 6, 5, 4, 7]
n = len(arr)
quickSortIterative(arr, 0, n - 1)
print("정렬된 배열:")
for i in range(n):
print(arr[i], end=" ")실행 결과
정렬된 배열: 2 3 4 5 5 6 7 8
동작 원리 정리
위 코드에서 모든 변수는 지역 범위(local scope) 내에서 선언되며, 각 단계의 참조 관계는 다음과 같습니다.
- partition(): 마지막 요소를 피벗으로 삼아, 피벗보다 작거나 같은 값들은 왼쪽으로, 큰 값들은 오른쪽으로 이동시킨 뒤 피벗의 최종 위치 인덱스를 반환합니다.
- quickSortIterative(): 명시적인 스택 배열에 정렬할 구간의 시작 인덱스와 끝 인덱스를 저장하고, while 루프를 통해 구간을 하나씩 꺼내 분할 작업을 수행합니다.
- 재귀 호출이 스택 프레임을 사용하는 것과 달리, 이 방식은 직접 만든 스택으로 호출 순서를 관리하므로 재귀 깊이 제한(recursion limit)에 영향을 받지 않습니다.
결론
이번 글에서는 파이썬에서 재귀 함수 대신 스택 자료구조를 활용하여 퀵 정렬을 반복적(iterative) 방식으로 구현하는 방법을 알아보았습니다. 이 기법은 데이터 크기가 매우 커서 재귀 깊이 제한에 걸릴 위험이 있는 경우에 특히 유용하게 활용할 수 있습니다.