🧩 Dual-Pivot Quicksort

---

 

핵심 개념

• Quicksort는 pivot 1개를 사용해 배열을 두 부분으로 나누지만, Dual-Pivot Quicksort는 pivot 2개를 사용해 배열을 세 부분으로 나눕니다.
• 각 구간을 재귀적으로 정렬하는 고성능 분할 정복 기반 정렬 알고리즘입니다.
• Arrays.sort()에 사용되고 있습니다.

---

분할 방식(Pivot 2개 → 3 구간)

1. pivot1 < pivot2 범위 선정
2. 배열을 다음 3개의 부분으로 나눔:
   • arr[i] < pivot1
   • pivot1 ≤ arr[i] ≤ pivot2
   • arr[i] > pivot2
3. 이 3개 구간을 각각 재귀적으로 정렬

---

동작 절차 구현

• 아래 소스는 이해를 위해 만든 로직입니다. Arrays.sort()와는 접근 방식이 다릅니다.
• 결과값은 같습니다.

void dualPivotSort(int[] arr, int left, int right) {
    if (left < right) {
        // 1. 피벗 두 개 선택
        int pivot1 = arr[left];
        int pivot2 = arr[right];

        // 2. 피벗 순서 보정
        if (pivot1 > pivot2) {
            swap(arr, left, right);
            pivot1 = arr[left];
            pivot2 = arr[right];
        }

        // 3. 분할 및 정렬
        int lt = left + 1;
        int gt = right - 1;
        int i = lt;

        while (i <= gt) {
            if (arr[i] < pivot1) {
                swap(arr, i++, lt++);
            } else if (arr[i] > pivot2) {
                swap(arr, i, gt--);
            } else {
 				i++;
            }
        }

		// 피봇 제자리 이동
        swap(arr, left, --lt);
        swap(arr, right, ++gt);

        // 4. 재귀 호출 
		if (lt - left > 1) dualPivotSort(arr, left, lt - 1);  
		if (gt - lt > 1) dualPivotSort(arr, lt + 1, gt - 1);  
		if (right - gt > 1) dualPivotSort(arr, gt + 1, right);
    }
}
void swap(int[] arr, int i, int j) {
    if(i == j) return;
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

---

실제 동작 절차 요약

1. Arrays.sort(배열) 을 전달
2. 내부적으로 DualPivotQuicksort.sort(배열, 병렬계산 수, low, high ) 호출
3. 피봇을 고르게 5개의 샘플링 데이터를 지정한다.
   • 실험적 튜닝을 통한 최적값 step 이라는 값으로 샘플링을 보정한다.
4. 5개의 샘플링을 통해 고르게 분포되어있으면 듀얼 피봇 알고리즘을 사용하여 정렬한다.
   1) 중앙(피봇1 ~ 피봇2) 사이를 순회하여 스왑하면서 정렬한다.
   2) 그 외 값들은 좌/우로 스왑하고 중앙을 제외하고 재귀 호출한다.
   3) 샘플림은 검증을 더 원할하게 하는 장치일 뿐이다.
   5) 그렇지 않다면 단일 피봇 알고리즘을 사용하여 좌/우 스왑하여 정렬한다.
   • 중복된 값은 넘어간다.
   • 상단 구역을 재귀한다.
   • 하단 구역은 샘플링된 최소값을 최대값으로 전달하여 내부적으로 반복한다.
5. 반복을 통해 사이즈가 점점 줄어들면서 내부적으로 삽입정렬, 힙정렬으로 변환하여 정렬한 값을 반환한다.
   • 여러 조건에 범위에 따라 성능 차이가 나기 때문에 정렬 알고리즘을 조합하여 사용하는 것이다.

자세한 사항은 java.util.DualPivotQuicksort.sort()를 찾아보거나 댓글 남겨주시면 답변드리겠습니다.

---

🔍 성능 비교

알고리즘	평균 시간복잡도	최악의 경우	실제 Java 적용
단일 피벗 퀵정렬	O(n log n)	O(n²)	과거 Java 6 이하
Dual-Pivot 퀵정렬	O(n log n)	O(n²)	Java 7 이상 Arrays.sort(int[])

성능 향상 포인트:

• 중간 값이 많은 경우, 중앙 구간을 효율적으로 정렬
• 피벗 2개로 인해 분할 균형성이 좋아짐
• 대부분의 실무 데이터에서 기존 퀵정렬보다 10~30% 빠름

📈 실측 차이 예시 (OpenJDK 커밋 기준)

javac나 java.util.Arrays.sort()에서 듀얼 피봇이 채택된 이유도 아래와 같습니다:

입력 유형	단일 피봇 평균	듀얼 피봇 평균
무작위 배열	1.0x	1.21.5x 빠름
중복 많은 배열	1.0x	~1.7x 빠름
정렬된 배열	퇴화 위험	안정 처리

 

---

🧠 정리

Dual-Pivot Quicksort는 두 개의 피벗을 사용해 배열을 세 부분으로 나누어 정렬하는 퀵정렬의 개선형으로, Java 7부터 기본 정렬 알고리즘으로 채택되어 고성능을 제공합니다.
현대 컴퓨터 아키텍처에서의 실제 성능은 더 우수할 수 있습니다. 이는 캐시 활용, 분기 예측, 메모리 접근 패턴 등 다양한 하드웨어 최적화 요소에 기인합니다.

---

참조

The new optimized version of Dual-Pivot Quicksort
Dual pivot Quicksort
Average Case Analysis of Java 7's Dual Pivot Quicksort
Why Is Dual-Pivot Quicksort Fast?