Dual-Pivot Quick Sort 알고리즘 구현하기
이번에는 자바로 Dual-Pivot Quick Sort 알고리즘을 직접 구현해보겠습니다
이전에 사용했던 [8, 4, 7, 3, 9, 2, 6, 5, 1] 배열을 오름차순 정렬할 것입니다
Dual-Pivot Quick Sort 알고리즘 구현 - Java
public class Main {
public static void main(String[] args){
int[] arr = {8, 4, 7, 3, 9, 2, 6, 5, 1};
dualPivotQuickSort(arr, 0, arr.length-1);
System.out.print(Arrays.toString(arr));
}
private static void dualPivotQuickSort(int[] arr, int low, int high){
if(low < high){
if(arr[low] > arr[high]){
swap(arr, low, high);
}
int l = arr[low];
int r = arr[high];
int lt = low + 1;
int gt = high - 1;
int now = lt;
while(now <= gt){
if(arr[now] < l){
swap(arr, now++, lt++);
}else if(arr[now] > r){
swap(arr, now, gt--);
}else{
now++;
}
}
swap(arr, low, --lt);
swap(arr, high, ++gt);
dualPivotQuickSort(arr, low, lt-1);
dualPivotQuickSort(arr, lt+1, gt-1);
dualPivotQuickSort(arr, gt+1, high);
}
}
private static void swap(int[] arr, int low, int high){
if(low != high){
int tmp = arr[low];
arr[low] = arr[high];
arr[high] = tmp;
}
}
}위와같이 구현했습니다
구현 프로세스는 이전 동작과정과 동일합니다
먼저 배열의 양 끝을 두 피벗으로 잡아줍니다
이후, 만약 low > high 인경우, 두 피벗의 값을 swap합니다
l은 기준 피벗의 왼쪽 값r은 기준 피벗의 오른쪽 값입니다
이어서 탐색 범위와 현재 어떤 인덱스를 가리키는지 나타낼 변수를 선언합니다
lt: 범위의 맨 왼쪽gt: 범위의 맨 오른쪽now: 현재 가리키는 인덱스
now와 lt, gt를 활용해 세 파티션으로 나뉘어지도록 탐색하며 swap합니다
최종 완성한 결과를 low와 high와 --lt, ++gt를 swap하며 다음 탐색을 준비합니다
나누어진 3개의 파티션별로 각각 재귀 함수를 실행하여 정렬은 반복합니다
결과 확인
결과: [1, 2, 3, 4, 5, 6, 7, 8, 9]
위와같이 오름차순 정렬된 결과를 확인할 수 있습니다
Arrays.sort()에서 Dual-Pivot Quick Sort를 사용하는 이유
Java의 Arrays.sort()는 원시 타입 배열(int[], double[])에 대해
Dual-Pivot Quick Sort 알고리즘으로 정렬합니다
이는 Java 7부터 적용된 방식입니다
이 알고리즘이 채택된 이유는 다음과 같습니다
더 적은 비교횟수로 인한 성능 향상
Dual-Pivot Quick Sort는 배열을 두 개의 피벗을 기준으로 세 부분으로 분할하여 정렬하기 때문에
단일 피벗 Quick Sort보다 더 균형 잡힌 분할이 가능하고
그 결과 평균 비교 횟수와 교환 횟수가 줄어듭니다
또한 각 분할 구간의 크기가 작아지므로
재귀 호출 깊이도 얕아져 전체적인 성능이 향상됩니다
낮은 메모리 사용량
병합 정렬처럼 별도의 배열을 생성하지 않기 때문에 in-place 정렬이 가능하며 메모리 사용량이 적습니다
참조 지역성 이점
배열을 순차적으로 접근하는 구조이기 때문에 CPU 캐시의 참조 지역성을 활용할 수 있습니다
이는 캐시 미스를 줄이고 실행 속도를 향상시키는데 도움을 줍니다
이때, Java의 int[], double[] 같은 원시 타입 배열은 데이터가 연속된 메모리 공간에 저장됩니다
배열 요소를 순차적으로 접근하는 정렬 방식은 참조지역성의 이점을 극대화할 수 있습니다
반면, Integer[], String[] 같은 참조 타입 배열은 배열에 실제 값이 아닌 객체의 참조가 저장되므로,
값에 접근할 때마다 Heap 메모리의 임의 위치를 간접적으로 참조해야 합니다
따라서 Arrays.sort()는 원시타입 배열에 대해 Dual-Pivot Quick Sort 알고리즘을 적용하고 있습니다
