퀵 정렬(Quick Sort)의 개념
퀵 정렬은 분할 정복(Divide and Conquer) 방식을 통해 데이터를 정렬하는 방식입니다. 피벗(pivot) 이라고 불리는 특정 원소를 기준으로 주어진 배열을 두 부분배열로 분할하고, 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용해 데이터를 정렬하게 됩니다.
아래와 같은 흐름을 이용해 데이터를 정렬합니다.
- 피벗 선택: 배열에서 하나의 요소를 선택합니다. 이 요소를 피벗(pivot)이라고 합니다. 피벗의 선택 방법은 다양하며, 이는 퀵 정렬의 성능에 큰 영향을 미칠 수 있습니다. 가장 간단한 방법은 배열의 첫 번째 요소나 마지막 요소를 피벗으로 선택하는 것입니다.
- 분할(Partitioning): 피벗을 기준으로 배열을 두 부분으로 나눕니다. 첫 번째 부분에는 피벗보다 작은 모든 요소들이 오고, 두 번째 부분에는 피벗보다 큰 모든 요소들이 옵니다. 이 과정에서 피벗은 최종 정렬 위치로 이동하게 됩니다.
- 정복(Conquer): 분할된 두 부분에 대해 재귀적으로 퀵 정렬을 수행합니다.
퀵 정렬의 Python 구현
Python 으로 퀵 정렬을 아래와 같이 구현할 수 있습니다.
def quick_sort(arr: list, n: int) -> None:
if n <= 1:
return
pivot = _partition(arr, n - 1)
quick_sort(arr, pivot)
quick_sort(arr[pivot + 1 :], n - pivot - 1)
def _partition(arr: list, n: int) -> int:
pivot = arr[n]
i = -1
for j in range(n):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[n] = arr[n], arr[i + 1]
return i + 1
위의 코드는 아래와 같이 동작합니다.
quick_sort에서, 분할 함수_partition()을 호출해, 피벗을 기준으로 배열을 두 부분배열로 분할합니다.- 왼쪽 부분배열에 대해서 퀵 정렬을 수행하고, 오른쪽 부분배열에 대해서 퀵 정렬을 재귀적으로 호출해 정렬을 완료합니다.
아래와 같은 배열에서, 먼저 _partition 이 호출됩니다. 피벗은 70이 되고, 70을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동하게 됩니다.
- + - + - - ^ (pivot)
[10, 80, 30, 90, 40, 50, 70]
# 정렬 이후 ^ (pivot)
[10, 30, 40, 50, 70, 90, 80]
피벗을 기준으로 이제 왼쪽 배열과 오른쪽 배열이 나누어졌는데, 위의 과정처럼 왼쪽 배열에 대해서 퀵 정렬을 수행하고, 이어서 오른쪽 배열에 대해서 퀵 정렬을 수행하여 정렬을 완료합니다.
^ | ^ # 50을 기준으로 quick_sort, 80을 기준으로 quick_sort
[10, 30, 40, 50, 70, 90, 80]
# 왼쪽 부분 정렬
^ | | ^
[10, 30, 40, 50, 70, 90, 80]
...
# 왼쪽 부분 정렬 완료
| | | | | ^
[10, 30, 40, 50, 70, 90, 80]
# 오른쪽 부분 정렬 완료
| | | | | | |
[10, 30, 40, 50, 70, 90, 80]
퀵 정렬의 성능 분석과 특징
- 최악의 경우,
O(n^2)의 시간 복잡도를 가집니다.- 예컨대 최악의 경우는 배열이 이미 정렬된 상태이거나, 역순으로 정렬되어 있고 피벗을 배열의 가장 첫 번째 원소로 지정하는 경우가 있을 수 있습니다. 이러한 경우, 피벗만 제저리를 잡고 나머지 모든 원소가 하나의 부분배열이 됩니다.
- 마찬가지로, 피벗이 항상 최댓값이나 최솟값이 되는 경우 최악의 경우가 됩니다.
- 최선의 경우,
O(nlogn)의 시간 복잡도를 가집니다. - 평균적인 경우,
O(nlogn)의 시간 복잡도를 가집니다. - 최악의 경우 다른 정렬 알고리즘보다 빠르지 않지만, 피벗 설정의 임의성만 보장된다면 평균 성능(
O(nlogn)) 을 보일 가능성이 매우 높은 정렬 알고리즘입니다.