퀵 정렬의 피벗 전략과 메모리 내 정렬 운영

피벗으로 문제를 쪼개는 정렬 방식

퀵 정렬은 배열에서 피벗(Pivot)을 하나 고른 뒤, 그보다 작은 값과 큰 값을 양쪽으로 나누고 각 구간을 다시 정렬하는 분할 정복 기반 비교 정렬이다. 파티션 과정이 배열을 지속적으로 더 작은 문제로 분해한다.

평균 시간 복잡도는 O(n log n), 최악 시간 복잡도는 O(n^2)이다. 재귀 스택을 포함한 추가 메모리는 O(log n) 수준이며, 제자리(In-place) 구현이 가능하다. 같은 키의 원래 순서를 보장하지 않는 불안정 정렬이라는 점도 선택 기준에 포함해야 한다.

대규모 데이터를 메모리 안에서 정렬할 때 평균 성능과 낮은 추가 메모리 사용량이 함께 필요한 경우에 주로 고려된다. C++ 표준 sort의 Introsort 핵심 단계로도 활용된다.

피벗과 파티션이 성능을 좌우한다

피벗을 무작위로 고르거나 처음·중간·끝 값의 중앙값을 택하는 median-of-three 방식을 사용하면 정렬·역정렬·중복 치우침 데이터에서 최악 복잡도가 발생할 가능성을 낮출 수 있다.

파티션 구현은 대표적으로 Hoare와 Lomuto 방식으로 나뉜다. Hoare 방식은 양끝 포인터를 이동시키며 교차할 때까지 값을 교환하므로 스왑 횟수와 비교 연산 수가 감소하는 경향이 있다. Lomuto 방식은 한쪽 포인터를 따라가므로 구현은 단순하지만 성능은 Hoare 방식보다 다소 열세다.

동일한 값이 많이 몰린 입력이라면 3-way partition(Dutch National Flag)을 적용할 수 있다. 피벗보다 작은 값, 같은 값, 큰 값을 분리해 중복 값에 따른 성능 저하를 완화한다.

재귀 깊이는 정렬 로직의 일부다

퀵 정렬을 재귀 호출만으로 구현하면 파티션 불균형이 누적될 때 시스템 스택 오버플로 위험이 생길 수 있다. 작은 파티션부터 재귀로 처리하고 큰 파티션은 반복문으로 넘기면 최대 스택 깊이를 O(log n)으로 제한할 수 있다.

제자리 파티션은 추가 메모리 사용량을 줄인다. 배열의 가까운 위치를 반복적으로 접근하는 특성은 CPU 캐시 활용에도 유리해 메모리 대역폭 제약 환경에서 성능을 유지하는 데 도움이 된다.

안정 정렬이 요구되는 경우에는 인덱스를 보조키로 쓰거나 Merge Sort 같은 다른 알고리즘을 선택해야 한다.

메모리 안에서 순위를 만들고 파티션을 정렬할 때

시스템 라이브러리와 런타임의 일반 목적 정렬에서는 메모리 사용량을 아끼면서 평균 성능을 확보하기 위해 퀵 정렬 계열이 쓰인다. C/C++ qsort, C++ std::sort의 Introsort 내부 단계, 일부 JVM 구현의 primitive 타입 Arrays.sort가 여기에 해당한다.

DB·검색·스트리밍 엔진에서는 쿼리 실행 계획의 in-memory 정렬과 임시 결과 집합 정렬 파이프라인에 적용할 수 있다. 외부 정렬(external sort)로 넘어가기 전 로컬 파티션을 정렬하는 단계에서도 활용된다.

Top-K나 순위 처리에서는 Quickselect로 K번째 통계량을 구한 뒤 부분 정렬을 수행할 수 있다. 전체 정렬보다 비용을 줄일 수 있는 방식이다. SampleSort 같은 샘플링-파티셔닝 기반 분산 정렬에서는 각 파티션의 로컬 정렬로 사용되며, 스레드·코어 단위 병렬화에서도 캐시 친화적인 특성이 장점이 된다.

처리 흐름과 입력 조건

입력은 비교 가능한 요소로 구성된 배열 A[0..n-1]이다. 피벗을 선택한 뒤 Hoare, Lomuto, 3-way 방식 중 하나로 파티션하고, 좌우 부분 배열을 작은 쪽부터 재귀 처리한다. n ≤ 1이면 즉시 반환하며, 결과는 오름차순으로 정렬된 배열이다.

무작위 또는 median-of-three 피벗은 데이터 편향에 대응하는 수단이다. 꼬리 재귀 제거와 작은 파티션 우선 재귀는 스택 깊이를 제어한다. 평균 O(n log n) 시간 복잡도와 낮은 상수 계수는 처리량에 유리하고, 피벗 전략과 3-way 파티션은 최악 O(n^2) 상황 및 중복 치우침 데이터의 리스크를 완화한다.

다른 비교 정렬과의 선택 기준

알고리즘	성능(평균/최악)	확장성(메모리)	일관성(안정성)	안정성(최악 회피)	운영 편의
Quick Sort	O(n log n) / O(n^2)	O(log n) 스택	불안정	피벗 전략·3-way로 완화	제자리, 구현 용이, 캐시 우수
Merge Sort	O(n log n) / O(n log n)	O(n) 보조 배열	안정	일관된 성능	외부정렬·스트림에 적합
Heap Sort	O(n log n) / O(n log n)	O(1)	불안정	일관된 성능	캐시 비우호, 상수계수 큼

Hoare 파티션과 스택 깊이 제어 구현

아래 구현은 무작위 피벗을 사용하는 Hoare 파티션을 바탕으로 한다. 작은 쪽을 먼저 재귀 호출하고 큰 쪽은 반복 처리해 재귀 깊이를 제한한다.

# quick_sort.py
# Python 3.10+
from random import randint
from typing import List, TypeVar

T = TypeVar("T")

def quick_sort(a: List[T]) -> List[T]:
    if len(a) <= 1:
        return a

    def partition(lo: int, hi: int) -> int:
        # Hoare partition with randomized pivot
        p = randint(lo, hi)
        pivot = a[p]
        i, j = lo - 1, hi + 1
        while True:
            i += 1
            while a[i] < pivot:
                i += 1
            j -= 1
            while a[j] > pivot:
                j -= 1
            if i >= j:
                return j
            a[i], a[j] = a[j], a[i]

    def sort(lo: int, hi: int) -> None:
        while lo < hi:
            p = partition(lo, hi)
            # recurse on smaller side first to cap recursion depth
            if p - lo < hi - (p + 1):
                sort(lo, p)
                lo = p + 1
            else:
                sort(p + 1, hi)
                hi = p

    sort(0, len(a) - 1)
    return a

if __name__ == "__main__":
    data = [9, 3, 7, 1, 8, 2, 5, 6, 4, 0, 3, 3]
    print(quick_sort(data))  # 정렬 결과 출력

이 구현의 평균 시간 복잡도는 O(n log n)이고 최악 시간 복잡도는 O(n^2)이다. 추가 공간은 O(log n) 재귀 스택이며, 꼬리 재귀 제거로 최대 깊이를 제한한다.

동일 값이 매우 많은 데이터는 3-way partition으로 교체할 수 있다. 이미 정렬되었거나 역정렬에 가까운 데이터에서는 median-of-three 또는 무작위 피벗이 필요하다.