[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