: Dual-Pivot QuickSort(이중 피벗 퀵소트)는 전통적인 QuickSort(퀵 정렬)의 변형으로, 이름 그대로 두 개의 피벗(pivot)을 사용하여 배열을 세 부분으로 나누고 재귀적으로 정렬하는 방식이다.
: 이 방식은 Java의 Arrays.sort()에서 기본 정렬 알고리즘으로 채택될 만큼 성능이 뛰어난 것으로 알려져 있다.
✅ Dual-Pivot QuickSort 개념
기본 아이디어:
- 일반적인 QuickSort는 하나의 피벗을 기준으로 배열을 두 부분으로 나눔.
- Dual-Pivot QuickSort는 두 개의 피벗을 사용해 배열을 세 부분으로 나눔:
- 첫 번째 피벗보다 작은 값들
- 두 피벗 사이의 값들
- 두 번째 피벗보다 큰 값들
정렬 단계:
- 배열에서 두 개의 피벗을 선택 (pivot1, pivot2)
- 일반적으로 배열의 양 끝 요소 선택 (left, right)
- pivot1 < pivot2 가 되도록 보장
- 배열을 다음 세 영역으로 나눔:
- pivot1보다 작은 값
- pivot1과 pivot2 사이의 값
- pivot2보다 큰 값
- 세 영역 각각에 대해 재귀적으로 Dual-Pivot QuickSort 수행
분할 예시:
초기 배열: [9, 2, 7, 4, 5, 1, 8, 3, 6]
피벗 선택: pivot1 = 2, pivot2 = 7
나누기 결과:
- 작은 그룹: [1]
- 중간 그룹: [4, 5, 3, 6]
- 큰 그룹: [9, 8]
피벗 기준 재배치 후: [1] 2 [4,5,3,6] 7 [9,8]
→ 세 그룹에 대해 재귀 정렬시간 복잡도
| 경우 | 시간 복잡도 |
|---|---|
| 평균 | O(n log n) |
| 최악 | O(n²) (불균형하게 나눌 경우) |
| 최선 | O(n log n) |
하지만 일반적으로 Dual-Pivot QuickSort는 QuickSort보다 빠르게 동작한다.
이유는:
- 메모리 접근을 줄이는 최적화
- 피벗이 두 개라 더 균형 있게 나눌 가능성
✔️ 특징 정리
| 항목 | 내용 |
|---|---|
| 피벗 수 | 2개 |
| 파티션 수 | 3개 |
| 장점 | 실제 성능 향상 (캐시 효율, 더 적은 비교), Java 표준 |
| 단점 | 구현이 복잡함, 최악의 경우 여전히 O(n²) |
💡 활용 예
- Java의 Arrays..sort(int[])에서 Dual-Pivot QuickSort를 사용 (Java 7부터)
- 입력이 정수형 배열이고, 요소 개수가 작지 않다면 매우 효율적
✅ 피벗(Pivot)의 역할
- 배열에서 하나의 값을 선택해서, 이 값을 기준으로:
- 작은 값들은 피벗 왼쪽으로,
- 큰 값들은 피벗 오른쪽으로 보낸다.
- 이렇게 분할한 뒤, 왼쪽과 오른쪽 각각에 대해 재귀적으로 정렬한다.
예시
배열: [6, 3, 8, 5, 2]
피벗으로 5를 선택한다고 가정:
1. 5보다 작은 값 → [3, 2]
2. 5보다 큰 값 → [6, 8]
⇒ 분할 결과: [3, 2] + 5 + [6. 8]
⇒ 이 과정을 양쪽에 반복하면 정렬 완료
❗ 피벗 선택이 중요한 이유
- 좋은 피벗은 배열을 거의 반반으로 나눌 수 있어 성능이 좋다.
- 나쁜 피벗(예: 최댓값이나 최솟값만 계속 선택되면)은 분할이 비효율적이고, 성능이 O(n²)으로 떨어질 수 있다.
➕ 실제 Dual-Pivot QuickSort의 피벗 선택 방식
pivot1 = arr[left]; // 배열의 첫 번째 요소
pivot2 = arr[right]; // 배열의 마지막 요소
if (pivot1 > pivot2) {
swap(pivot1, pivot2); // 항상 pivot1 <= pivot2 되도록 정렬
}가장 왼쪽과 오른쪽 값을 피벗으로 삼는 것이 일반적
- 실제 Dual-Pivot QuickSort는 배열의 양 끝 값을 피벗으로 사용하는 경우가 많음
- 상황에 따라 중간 값이나 무작위 값을 피벗으로 선택하는 전략적 방법도 가능
