퀵정렬의 피벗 선택과 파티셔닝 전략

피벗이 배열을 나누는 방식

퀵정렬은 피벗을 하나 고른 뒤, 그보다 작은 값과 큰 값을 서로 다른 쪽으로 재배치하는 비교 정렬 알고리즘이다. 파티셔닝이 끝나면 배열은 피벗을 경계로 나뉘며, 각 부분배열에 같은 작업을 재귀적으로 적용한다.

평균 시간 복잡도는 O(n log n)이고 최악은 O(n^2)이다. 재귀 스택을 포함한 공간 복잡도는 O(log n)이다. 추가 메모리 사용이 적고 캐시 로컬리티가 좋아 정렬 구현에 자주 쓰인다. 표준 라이브러리에서는 피벗 선택과 힙소트·삽입정렬을 결합한 IntroSort로 최악 성능을 피하는 구성을 사용하기도 한다.

⤢✕

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

피벗은 정중앙 원소, 랜덤 원소, 또는 좌·중·우 값의 중간값인 median-of-three 방식으로 선택할 수 있다. 이미 정렬된 배열이나 역순 배열에서의 최악 상황을 줄이려면 랜덤 선택이나 median-of-three를 고려한다.

Hoare 파티션은 배열 양끝의 포인터를 안쪽으로 옮기며, 포인터가 교차할 때까지 원소를 교환한다. 교환 횟수가 적고 빠른 편이다. Lomuto 파티션은 하나의 스캔과 경계 인덱스로 분할하므로 구현은 단순하지만 교환 횟수가 늘어날 수 있다.

재귀 호출에서는 작은 쪽을 먼저 처리하고 큰 쪽을 반복문으로 이어가면 최대 스택 깊이를 O(log n)으로 유지할 수 있다. 명시적 스택을 쓰는 비재귀 방식은 스택 오버플로 위험을 더 줄이는 선택지다.

작은 구간, 예를 들어 길이 ≤ 16에서는 삽입정렬로 전환해 성능을 높일 수 있다. 퀵정렬은 같은 키의 상대적 순서를 보장하지 않는 불안정 정렬이며, 제자리 정렬로 추가 메모리 사용량이 낮다.

정렬 경로에서 퀵정렬을 고를 때

애플리케이션의 내장 정렬 엔진에서는 대규모 정수나 키-값 페어를 평균적으로 빠르게 정렬하는 용도로 적합하다. JVM과 네이티브 라이브러리의 IntroSort 백본에도 활용된다.

서비스 로그나 이벤트처럼 평균 응답시간이 중요한 정렬 경로, 짧은 구간을 반복적으로 정렬하는 처리에서도 캐시 효과를 활용할 수 있다. 데이터 엔지니어링에서는 맵리듀스 단계의 로컬 정렬과 샘플링 기반 파티셔닝 전처리에 연결할 수 있으며, Quickselect와 결합해 상위 K를 추출하는 데도 쓰인다.

n = 10^6일 때 n log2 n은 약 20M 비교 수준이고, O(n^2)/2는 약 5e11 비교 수준이다. 실제 성능은 데이터 분포, 분기 예측, 메모리 대역폭의 영향을 받는다. 재귀 스택은 평균 O(log n)이며 병합정렬과 비교하면 보조 메모리를 줄일 수 있다. 캐시 친화적 접근 패턴은 환경에 따라 1.2~2.0배 체감 성능 향상 사례가 있다.

Hoare 파티션으로 구현한 정렬 루프

전제조건: Java 11+, 원시 int 배열, null 방어, 작은 구간 삽입정렬 전환(옵션)

import java.util.Arrays;

public class QuickSort {
    private static final int INSERTION_SORT_THRESHOLD = 16;

    public static void quickSort(int[] a) {
        if (a == null || a.length < 2) return;
        quickSort(a, 0, a.length - 1);
    }

    private static void quickSort(int[] a, int left, int right) {
        while (left < right) {
            // 작은 구간은 삽입정렬로 전환
            if (right - left + 1 <= INSERTION_SORT_THRESHOLD) {
                insertionSort(a, left, right);
                return;
            }
            int p = partitionHoare(a, left, right);
            // 꼬리 재귀 제거: 작은 쪽 먼저 재귀 호출
            if (p - left < right - p) {
                quickSort(a, left, p);
                left = p + 1;
            } else {
                quickSort(a, p + 1, right);
                right = p;
            }
        }
    }

    // Hoare partition: 반환값 p에 대해 [left..p] ≤ pivot, [p+1..right] ≥ pivot
    private static int partitionHoare(int[] a, int left, int right) {
        int pivot = a[(left + right) >>> 1]; // 가운데 피벗
        int i = left - 1;
        int j = right + 1;
        while (true) {
            do { i++; } while (a[i] < pivot);
            do { j--; } while (a[j] > pivot);
            if (i >= j) return j;
            swap(a, i, j);
        }
    }

    private static void insertionSort(int[] a, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int key = a[i], j = i - 1;
            while (j >= left && a[j] > key) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
        }
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }

    // 샘플 실행
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5, 6, 7, 3, 8, 4};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

가운데 피벗은 구현을 단순하게 유지하면서 평균 성능을 확보한다. Hoare 파티션의 반환값 p를 기준으로 [left..p]와 [p+1..right]를 나누며, 작은 구간의 삽입정렬 전환과 꼬리 재귀 제거가 실제 스택 사용을 낮춘다.

사용자 제시 코드에는 partition 내부 조건 괄호가 누락된 문제가 있을 수 있다. Hoare와 Lomuto는 경계 처리와 반환 인덱스 규약이 다르므로, 선택한 방식에 맞춰 재귀 구간을 일관되게 설정해야 한다.

입력 경계와 중복 값 처리

입력은 배열, 좌·우 경계, 비교 함수로 구성하며 기본 정렬 방향은 오름차순이다. 피벗을 선택한 뒤 양쪽 포인터를 이동시키고, 교차 전까지 교환한 다음 분할을 끝낸다. 작은 구간 최적화와 꼬리 재귀 제거는 이 처리 흐름에 결합할 수 있다. 결과는 오름차순으로 정렬된 배열이다.

모든 원소가 같을 때는 빠른 조기 정지가 보장되며 Hoare 방식이 유리하다. 이미 정렬됐거나 역정렬된 입력은 랜덤 또는 median-of-three 피벗으로 최악 케이스를 방지한다. 중복 키가 큰 입력에서는 3-way 파티셔닝으로 교환과 비교를 줄일 수 있다.

병합정렬·힙정렬과의 선택 기준

알고리즘	성능(평균/최악)	확장성/캐시	일관성(안정성)	안정성(최악 회피)	운영 편의(메모리)
퀵정렬	O(n log n) / O(n^2)	매우 우수	불안정	피벗/IntroSort로 완화	매우 낮음(O(log n))
병합정렬	O(n log n) / O(n log n)	보통	안정	일관된 성능	추가 메모리 O(n)
힙정렬	O(n log n) / O(n log n)	보통	불안정	일관된 성능	낮음(O(1))

평균 성능과 메모리 효율이 우선이면 퀵정렬이 유력하다. 안정 정렬이 필요하거나 최악 성능의 일관성이 더 중요하면 병합정렬과 힙정렬의 특성을 함께 검토한다. 퀵정렬을 선택했다면 피벗 전략, 작은 구간 최적화, 꼬리 재귀 제거, IntroSort 채택 여부가 운영 특성에 맞아야 한다.