[Java] java.util의 Arrays.sort()는 어떤 정렬 알고리즘을 사용할까?
정렬 알고리즘을 배우며 병합 정렬, 퀵 정렬 등 다양한 종류의 알고리즘에 대해 배웠습니다. 그렇다면 자바에서 자주 사용하는 Arrays.sort() 는 어떤 알고리즘으로 구현되어있는지 궁금해졌습니다.
구글링과 자바 내부코드를 보면, Arrays.sort는 듀얼 피봇 퀵소트를 사용한다라고 나와있습니다.
Arrays.sort 메서드 내부를 들여다보면서, 듀얼 피봇 퀵소트란 무엇인지 그리고 범위에 따라 어떤 정렬 방식을 적용하는지를 알 수 있었습니다.
Arrays.sort() 내부 들여다보기
int[] arr = {1, 3, 4, 2, 1 ,7};
Arrays.sort(arr)
---
result: {1, 1, 2, 3, 4 ,7}
보통 자바에서 배열을 정렬할 때, java.util.Arrays 클래스의 sort()를 이용해 위와 같이 정렬합니다.
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
java.util.Arrays의 sort() 메서드는 DualPivotQuicksort 클래스를 사용하는 것을 볼 수 있습니다.
DualPivotQuicksort
우선 듀얼 피봇 퀵소트란 퀵소트를 변형한 알고리즘입니다. 퀵 소트에서 하나의 피벗을 기준으로 배열을 분할하며 값을 정렬했다면, 듀얼 피봇 퀵소트는 두 개의 피봇을 사용해 배열을 분할하는 방식입니다.
아래는 DualPivotQuicksort 클래스의 sort 메서드입니다.
static void sort(long[] a, int left, int right,
long[] work, int workBase, int workLen) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
/*
* Index run[i] is the start of i-th run
* (ascending or descending sequence).
*/
int[] run = new int[MAX_RUN_COUNT + 1];
int count = 0; run[0] = left;
// Check if the array is nearly sorted
for (int k = left; k < right; run[count] = k) {
if (a[k] < a[k + 1]) { // ascending
while (++k <= right && a[k - 1] <= a[k]);
} else if (a[k] > a[k + 1]) { // descending
while (++k <= right && a[k - 1] >= a[k]);
for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
long t = a[lo]; a[lo] = a[hi]; a[hi] = t;
}
} else { // equal
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
}
/*
* The array is not highly structured,
* use Quicksort instead of merge sort.
*/
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
}
// Check special cases
// Implementation note: variable "right" is increased by 1.
if (run[count] == right++) { // The last run contains one element
run[++count] = right;
} else if (count == 1) { // The array is already sorted
return;
}
// Determine alternation base for merge
byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
// Use or create temporary array b for merging
long[] b; // temp array; alternates with a
int ao, bo; // array offsets from 'left'
int blen = right - left; // space needed for b
if (work == null || workLen < blen || workBase + blen > work.length) {
work = new long[blen];
workBase = 0;
}
if (odd == 0) {
System.arraycopy(a, left, work, workBase, blen);
b = a;
bo = 0;
a = work;
ao = workBase - left;
} else {
b = work;
ao = 0;
bo = workBase - left;
}
// Merging
for (int last; count > 1; count = last) {
for (int k = (last = 0) + 2; k <= count; k += 2) {
int hi = run[k], mi = run[k - 1];
for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
b[i + bo] = a[p++ + ao];
} else {
b[i + bo] = a[q++ + ao];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
b[i + bo] = a[i + ao]
);
run[++last] = right;
}
long[] t = a; a = b; b = t;
int o = ao; ao = bo; bo = o;
}
}
위 sort() 메서드 코드를 통해 내부에서 작동하는 코드를 살펴보겠습니다.
1. 작은 배열에 대해 퀵소트/삽입 정렬 실행
private static final int QUICKSORT_THRESHOLD = 286;
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
주어진 배열이 작은 경우에는 간단한 퀵소트를 사용합니다. 이때 배열의 크기가 작고 적은 기준은 QUICKSORT_THRESHOLD = 286 기준으로 나뉩니다.
그리고 위에서의 sort() 메서드를 타고 들어가면, 아래와 같은 200줄 이상의 코드가 나오는데
여기서, 배열 크기가 더 작은 것은 삽입 정렬 알고리즘을 사용한다는 것을 알 수 있습니다. 이때의 배열 임계 값은 INSERTION_SORT_THRESHOLD = 47; 인 것을 알 수 있습니다.
private static final int INSERTION_SORT_THRESHOLD = 47;
...
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
if (leftmost) {
for (int i = left, j = i; i < right; j = ++i) {
int ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == left) {
break;
}
}
a[j + 1] = ai;
}
}
...
2. 거의 정렬된 배열에 대해 퀵소트 실행
주어진 배열이 이미 거의 정렬되어 있다고 판단되면 퀵소트를 사용합니다. 퀵소트는 거의 정렬된 배열에 대해서는 더 좋은 성능을 보이기 때문입니다.
For 문을 돌며 배열의 정렬 확인
// Check if the array is nearly sorted
for (int k = left; k < right; run[count] = k) {
if (a[k] < a[k + 1]) { // ascending
while (++k <= right && a[k - 1] <= a[k]);
} else if (a[k] > a[k + 1]) { // descending
while (++k <= right && a[k - 1] >= a[k]);
for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
}
} else { // equal
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
}
/*
* The array is not highly structured,
* use Quicksort instead of merge sort.
*/
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
}
배열의 정렬을 확인합니다. 이때 오름차순인지, 내림차순인지, 동일한 값이 연속적으로 나타나는지 등을 확인합니다. 그래서 만약 연속된 값의 길이가 MAX_RUN_LENGTH ( = 67) 과 같으면 거의 정렬되어 있다고 판단하며 퀵소트를 수행합니다.
3. byte, short / char 형 배열
(1) byte 배열
private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29;
static void sort(byte[] a, int left, int right) {
// Use counting sort on large arrays
if (right - left > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
int[] count = new int[NUM_BYTE_VALUES];
for (int i = left - 1; ++i <= right;
count[a[i] - Byte.MIN_VALUE]++
);
for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {
while (count[--i] == 0);
byte value = (byte) (i + Byte.MIN_VALUE);
int s = count[i];
do {
a[--k] = value;
} while (--s > 0);
}
} else { // Use insertion sort on small arrays
for (int i = left, j = i; i < right; j = ++i) {
byte ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == left) {
break;
}
}
a[j + 1] = ai;
}
}
}
배열의 크기가 COUNTING_SORT_THRESHOLD_FOR_BYTE ( = 29) 보다 크면 카운팅 정렬을 사용하고, 작다면 삽입 정렬을 사용하는 것을 볼 수 있습니다.
(2) short / char 배열
private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;
static void sort(short[] a, int left, int right,
short[] work, int workBase, int workLen) {
// Use counting sort on large arrays
if (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
int[] count = new int[NUM_SHORT_VALUES];
for (int i = left - 1; ++i <= right;
count[a[i] - Short.MIN_VALUE]++
);
for (int i = NUM_SHORT_VALUES, k = right + 1; k > left; ) {
while (count[--i] == 0);
short value = (short) (i + Short.MIN_VALUE);
int s = count[i];
do {
a[--k] = value;
} while (--s > 0);
}
} else { // Use Dual-Pivot Quicksort on small arrays
doSort(a, left, right, work, workBase, workLen);
}
}
배열의 크기가 COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR ( =3200) 보다 크면 카운팅 정렬을 사용하고, 작으면 듀얼 피봇 퀵 소트를 사용하는 것을 볼 수 있습니다.
정리
정리하자면 자바의 정렬 알고리즘은 듀얼 피봇 퀵소트를 사용하지만, 배열의 범위에 따라 다르게 작용합니다.
1. 작은 범위( QUICKSORT_THRESHOLD = 286)에 대해서는 퀵소트를 사용한다.
2. 그것보다 더 작은 범위(INSERTION_SORT_THRESHOLD = 47 ) 에 대해서는 삽입 정렬을 사용한다.
3. 거의 정렬된 배열에 대해서는 퀵소트를 사용한다.
(for문을 돌며 판단하며 오름차순, 내림차순, 동일한 값 반복(MAX_RUN_LENGTH ( = 67) 등의 상황)
4. byte 배열에 대해서는 기준 (COUNTING_SORT_THRESHOLD_FOR_BYTE = 29)보다 크면 카운팅 정렬, 작으면 삽입 정렬을 사용한다.
5. short/char 배열에 대해서는 기준(COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR =3200) 보다 크면 카운팅 정렬, 작으면 듀얼 피봇 퀵 소트를 사용한다.
참고자료
https://velog.io/@skwx50000/java-Arrays.sort%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90
https://m.blog.naver.com/qbxlvnf11/221336019745