퀵 정렬(Quick Sort)은 컴퓨터 과학에서 가장 널리 사용되는 정렬 알고리즘 중 하나입니다. 이 글에서는 파이썬을 활용해 퀵 정렬을 직접 구현하는 방법을 단계별로 살펴보겠습니다.
문제 정의
문제: 주어진 배열을 퀵 정렬(Quicksort) 개념을 이용하여 오름차순으로 정렬하는 것입니다.
퀵 정렬의 핵심 아이디어는 배열을 분할(Divide)하고, 각각의 분할된 부분 배열을 개별적으로 정렬한 뒤, 이를 다시 합쳐 최종적으로 정렬된 배열을 얻는 것입니다.
퀵 정렬의 작동 원리
퀵 정렬은 다음과 같은 과정으로 동작합니다.
- 배열에서 하나의 요소를 피벗(pivot)으로 선택합니다.
- 피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 배치합니다. 이 과정을 파티션(partition)이라고 합니다.
- 피벗을 기준으로 나뉜 두 개의 하위 배열에 대해 같은 과정을 재귀적으로 반복합니다.
아래 예제에서는 배열의 마지막 요소를 피벗으로 사용하는 Lomuto 파티션 방식을 채택했습니다.
구현 예제
# 분할(partition) 함수
def partition(arr, low, high):
i = (low - 1)
pivot = arr[high] # 피벗 요소
for j in range(low, high):
# 현재 요소가 피벗보다 작거나 같으면
if arr[j] <= pivot:
# 인덱스를 증가시키고 두 요소의 위치를 교환
i = i + 1
arr[i], arr[j] = arr[j], arr[i]
# 피벗을 올바른 위치로 이동
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return (i + 1)
# 퀵 정렬 함수
def quickSort(arr, low, high):
if low < high:
# 파티션 인덱스
pi = partition(arr, low, high)
# 피벗을 기준으로 좌우 부분 배열을 각각 정렬
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
# 메인 코드
arr = [2, 5, 3, 8, 6, 5, 4, 7]
n = len(arr)
quickSort(arr, 0, n - 1)
print("Sorted array is:")
for i in range(n):
print(arr[i], end=" ")
실행 결과
Sorted array is: 2 3 4 5 5 6 7 8
코드 상세 설명
partition() 함수 내부의 모든 변수(i, j, pivot)는 지역 범위(local scope)에서 선언되며, 각 반복 단계에서 다음과 같은 역할을 수행합니다.
- pivot: 현재 분할 대상 구간의 마지막 요소로, 기준값 역할을 합니다.
- i: 피벗보다 작은 요소들이 놓일 영역의 경계를 나타냅니다.
- j: 배열을 순회하며 피벗과 비교되는 현재 요소의 인덱스입니다.
순회가 끝나면 피벗을 자신의 최종 위치(i+1)로 옮기고, 그 인덱스를 반환하여 재귀 호출의 기준점으로 사용합니다.
시간 복잡도
- 최선/평균 경우: O(n log n)
- 최악의 경우: O(n²) — 이미 정렬된 배열에서 피벗 선택이 불균형하게 이루어질 때 발생합니다.
- 공간 복잡도: O(log n) — 재귀 호출 스택 깊이 기준
결론
이번 글에서는 파이썬으로 퀵 정렬 알고리즘을 구현하는 방법을 알아보았습니다. 퀵 정렬은 분할 정복(Divide and Conquer) 전략을 활용하는 대표적인 정렬 알고리즘으로, 평균적으로 매우 빠른 성능을 보여주기 때문에 실무에서도 폭넓게 활용됩니다. 코드를 직접 실행해 보면서 파티션 과정을 단계별로 추적해 보면 알고리즘의 원리를 더욱 확실하게 이해할 수 있습니다.