[Python] 퀵 정렬

퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 알고리즘을 기반으로 한 정렬 방법 중 하나다. 평균적으로 매우 빠른 성능을 보이며, 이번 글에서는 퀵 정렬의 원리와 구현 방법(재귀적, 비재귀적 방식) 그리고 시간 복잡도와 안정성까지 정리해보겠다.

---

1. 퀵 정렬이란?

퀵 정렬은 리스트를 정렬하는 알고리즘 중 하나로, 기준이 되는 원소(Pivot)를 설정하고 이를 기준으로 왼쪽에는 작은 값, 오른쪽에는 큰 값을 배치하는 과정을 반복하여 정렬을 수행한다. 일반적으로 매우 빠른 속도를 보이며, 평균적으로 O(n log n)의 시간 복잡도를 가진다.

---

2. 퀵 정렬의 원리

퀵 정렬은 다음과 같은 원리로 동작한다:

1. Pivot(피벗) 선택 → 배열에서 특정 값을 피벗으로 선택한다.
2. Partition(분할) → 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 배치한다.
3. 재귀적 정렬 → 분할된 두 개의 하위 배열을 다시 같은 방식으로 정렬한다.

이 과정을 반복하면 전체 배열이 정렬된다.

3. 재귀적인 퀵 정렬 구현

리스트 컴프리헨션 사용

from typing import MutableSequence

def qsort(a: MutableSequence) -> MutableSequence:
    if len(a) <= 1:
        return a
    
    pivot = a[len(a) // 2]  # 피벗을 배열의 가운데 요소로 선택
    left = [x for x in a if x < pivot]  # 피벗보다 작은 값들
    middle = [x for x in a if x == pivot]  # 피벗과 같은 값들
    right = [x for x in a if x > pivot]  # 피벗보다 큰 값들
    
    return quick_sort_recursive(left) + middle + quick_sort_recursive(right)

배열을 직접 수정하여 정렬(in-place)

def qsort(a: MutableSequence, left: int, right: int) -> None:
    pl = left
    pr = right
    x = a[(left + right) // 2]  # 피벗을 배열의 가운데 요소로 선택

    while pl <= pr:  
        while a[pl] < x: pl += 1  # 왼쪽에서 피벗보다 큰 값 찾기
        while a[pr] > x: pr -= 1  # 오른쪽에서 피벗보다 작은 값 찾기
        if pl <= pr:  # 교차되지 않았다면 교환
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1

    # 재귀적으로 왼쪽과 오른쪽 부분 정렬
    if left < pr: qsort(a, left, pr)
    if pl < right: qsort(a, pl, right)

재귀적 퀵 정렬 설명

• 리스트의 크기가 1 이하가 될 때까지 재귀적으로 호출한다.
• 피벗을 기준으로 작은 값, 같은 값, 큰 값으로 나누어 정렬을 진행한다.
• 리스트 컴프리헨션을 활용하여 간결하게 구현할 수 있다.

---

4. 비재귀적인 퀵 정렬 구현

재귀적인 퀵 정렬은 함수 호출이 중첩되므로 스택 오버플로우가 발생할 가능성이 있다. 이를 방지하기 위해 명시적으로 스택을 사용하여 비재귀적인 방법으로 구현할 수 있다.

from typing import MutableSequence

def qsort(a: MutableSequence, left: int, right: int) -> None:
    stack = [(left, right)]

    while stack:
        pl, pr = left, right = stack.pop()
        x = a[(left + right) // 2]
        
        while pl <= pr:
        	while a[pl] < x: pl += 1
            while a[pr] > x: pr -= 1
            if pl <= pr:
              a[pl], a[pr] = a[pr], a[pl]
              pl += 1
              pr -= 1

        if left < pr:
            stack.append((left, pr))
        if pl < right:
            stack.append((pl, right))

비재귀적 퀵 정렬 설명

• 명시적인 스택을 사용하여 반복문으로 구현한다.
• 파티션 과정을 거쳐 피벗을 기준으로 정렬한다.
• 스택을 활용하여 정렬할 구간을 관리한다.

---

5. 시간 복잡도 및 안정성

경우	시간 복잡도
평균	O(n log n)
최선	O(n log n)
최악	O(n^2)

• 평균적으로 O(n log n)의 성능을 보인다.
• 최악의 경우(이미 정렬된 배열에서 항상 최솟값 또는 최댓값을 피벗으로 선택할 경우) O(n^2)까지 성능이 저하될 수 있다.
• 랜덤 피벗 선택, Median-of-Three 기법 등을 사용하면 최악의 경우를 방지할 수 있다.

퀵 정렬은 안정적인가?

• 퀵 정렬은 불안정 정렬이다.
• 동일한 값이 존재할 경우, 정렬 후 상대적인 순서가 유지되지 않는다.
• 데이터의 순서가 중요한 경우(예: 데이터베이스 레코드 정렬)에는 병합 정렬(Stable Sort) 등을 고려해야 한다.

---

마무리

• 퀵 정렬은 빠르고 효율적인 정렬 알고리즘 중 하나이며, 대부분의 경우 O(n log n)의 성능을 보장한다.
• 하지만 최악의 경우 O(n^2)이 될 가능성이 있기 때문에 적절한 피벗 선택 전략이 필요하다.
• 또한, 안정적인 정렬이 필요하다면 다른 방법을 고려하는 것이 좋다.
• 재귀적, 비재귀적 구현 방식을 비교해 보며 상황에 맞는 방법을 선택하는 것이 중요하다.