듀얼 피벗 퀵 정렬 (Dual Pivot Quick Sort)
듀얼 피벗 퀵 정렬 (Dual Pivot Quick Sort)
듀얼 피벗 퀵 정렬은 Java의 Arrays.sort() 정렬 메소드에 사용되며 원시 타입(primitive type, int[], long[]) 배열을 정렬할 때 사용합니다. 퀵 정렬 보다 더 효율적이며, 두 개의 피벗을 사용하여 배열을 세 부분으로 나누어 정렬합니다.
시간 복잡도 : O(n log n) 최악의 경우 O(n^2)
듀얼 피벗 퀵소트는 원시 타입의 배열을 정렬할 때 사용합니다. 객체 타입일 때는 팀소트를 사용합니다.
원시 타입 배열 특징
- 원시 타입은 메모리 크기가 작아서 값 복사나 이동이 빠릅니다. 이로 인해 값의 비교가 빠릅니다.
- 원시 타입 배열들은 메모리에 연속적으로 저장하여 메모리에 빠르게 접근할 수 있습니다.
듀얼 피벗 퀵 정렬 특징
- 듀얼 피벗 퀵 정렬은 퀵 정렬과 달리 2개의 피벗을 사용하여 세 부분으로 나눕니다. (퀵 정렬 보다 빠름)
- 세 부분으로 나누기 위해 값의 비교와 이동이 자주 일어납니다.
듀얼 피벗 퀵 정렬은 값을 비교하고 이동하여 정렬을 하므로 원시 타입 배열의 비교가 쉽고 이동이 빠르다는 특징과 맞물려 효율적으로 정렬할 수 있습니다. 이로 인해 Java의 원시 타입 배열에 듀얼 피벗 퀵 정렬을 사용합니다.
동작 과정
듀얼 피벗 퀵 정렬은 피벗 선택으로 배열을 세 부분으로 나누고 나누어진 세 부분을 또 두 개의 피벗을 선택하고 세 부분으로 나눕니다. 이렇게 재귀적으로 동작하여 정렬을 완성합니다.
1. 피벗 선택
두 개의 피벗 p1, p2를 선택합니다. p1 < p2 조건을 만족하도록 합니다. 일반적으로 배열의 첫 번째 요소와 마지막 요소를 사용합니다.
2. 분할
두 개의 피벗 p1, p2를 기준으로 3개로 분할 합니다.
3. 재귀
분할된 3부분에서도 피벗 2개를 선택하여 3개로 나눕니다. 이 과정을 가장 작은 영역까지 거쳐 정렬된 전체 배열을 얻습니다.
예시
예시 배열 : [3, 1, 5, 9, 4, 8, 7]
1. 피벗 선택 :
두 개의 피벗을 선택합니다. 일반적으로 배열의 첫 번째 요소와 마지막 요소를 사용합니다.
[3, 1, 5, 9, 4, 8, 7]
2. 분할
두 개의 피벗을 기준으로 3개로 분할합니다. 피벗을 p1, p2로 p1 < p2 를 만족하도록 합니다.
왼쪽 부분 : p1 보다 작은 요소
가운데 부분 : p1과 p2 사이의 요소
오른쪽 부분 : p2 보다 큰 요소
[1] 3 [5, 4] 7 [9, 8]
3. 재귀
나누어진 부분도 위의 과정을 거쳐 정렬을 완성합니다.
[1, 3, 4, 5, 7, 8, 9]
Java 코드 구현
/*
듀얼 피봇 퀵소트 Dual Pivot Quick Sort
시간 복잡도
평균 - O(n log n)
최악의 경우 - O(n^2)
Java의 sort 메소드에서 프리미티브 타입의 배열을 정려할 때 사용
두 개의 피벗을 선택하여 3개의 영역으로 나눈 후 정렬을 진행한다.
퀵소트보다 효율적이다.
*/
public class DualPivotQuickSort {
public static void main(String[] args) {
int[] array = {3,1,5,9,4,8,7};
printArray(array);
dualPivotQuickSort(array);
printArray(array);
}
// 메소드 시작
public static void dualPivotQuickSort(int[] array) {
dualPivotQuickSort(array, 0, array.length-1);
}
// 듀얼 피벗 퀵소트 정렬 시작
// 피벗 2개를 설정하여 영역을 정렬
public static void dualPivotQuickSort(int[] array, int low, int high) {
if(low < high) {
// high 큰 값, low 작은 값으로 설정
if(array[low] > array[high]) {
swap(array, low, high);
}
int pivot1 = array[low];
int pivot2 = array[high];
int lt = low + 1; // 피벗1보다 작은 요소들의 경계
int gt = high - 1; // 피벗2보다 큰 요소들의 경계
int i = low + 1; // 현재 검사 중인 요소
// p1 시작점, p2 끝점
// p1과 p2 사이를 탐색하면서 p1보다 작으면 왼쪽으로 보내고 p2보다 크면 오른쪽으로 보낸다.
// 이 과정에서 lt++, gt-- 과정이 이루어진다.
// 탐색을 마치면 p1, p2를 위치를 재조정한다.
// 같은 과정을 반복한다.
while(i <= gt) {
if(array[i] < pivot1) {
swap(array, i++, lt++);
}
else if(array[i] > pivot2) {
swap(array, i, gt--);
}
else {
i++;
}
}
swap(array, low, --lt);
swap(array, high, ++gt);
// 재귀적으로 정렬
dualPivotQuickSort(array, low, lt-1);
dualPivotQuickSort(array, lt+1, gt-1);
dualPivotQuickSort(array, gt+1, high);
}
}
// 위치 교환 메소드
public static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
public static void printArray(int[] array) {
for(int number : array) {
System.out.print(number + " ");
}
System.out.println();
}
}
마무리
이번에는 Arrays.sort()에서 원시 타입 배열에 사용하는 듀얼 피벗 퀵 정렬을 정리했습니다.
다음에는 객체 배열에 사용하는 팀 정렬(TimSort)에 대해 정리하겠습니다.
감사합니다.