[Java 파헤쳐보기] java.util의 Arrays.sort()는 어떤 정렬 알고리즘을 사용할까?

2024. 5. 20. 11:49· Java/Java 를 파헤쳐보자
목차
  1. Arrays.sort() 내부 들여다보기
  2. DualPivotQuicksort
  3. 1. 작은 배열에 대해 퀵소트/삽입 정렬 실행
  4. 2. 거의 정렬된 배열에 대해 퀵소트 실행
  5. 3. byte,  short / char 형 배열
  6. 정리
  7. 참고자료

 정렬 알고리즘을 배우며 병합 정렬, 퀵 정렬 등 다양한 종류의 알고리즘에 대해 배웠다. 그렇다면 자바에서 자주 사용하는 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

'Java > Java 를 파헤쳐보자' 카테고리의 다른 글

[Java 파헤쳐보기] Stack 대신 ArrayDeque를 써야하는 이유  (0) 2024.04.16
[Java 파헤쳐보기] ArrayDeque와 LinkedList  (4) 2024.04.13
[Java 파헤쳐보기] Java에서 ArrayList가 어떻게 구현되어 있을까?  (0) 2024.04.12
[Java 파헤쳐보기] Vector vs ArrayList  (0) 2024.04.11
[Java 파헤쳐보기] JCF 소개  (1) 2024.04.11
  1. Arrays.sort() 내부 들여다보기
  2. DualPivotQuicksort
  3. 1. 작은 배열에 대해 퀵소트/삽입 정렬 실행
  4. 2. 거의 정렬된 배열에 대해 퀵소트 실행
  5. 3. byte,  short / char 형 배열
  6. 정리
  7. 참고자료
'Java/Java 를 파헤쳐보자' 카테고리의 다른 글
  • [Java 파헤쳐보기] Stack 대신 ArrayDeque를 써야하는 이유
  • [Java 파헤쳐보기] ArrayDeque와 LinkedList
  • [Java 파헤쳐보기] Java에서 ArrayList가 어떻게 구현되어 있을까?
  • [Java 파헤쳐보기] Vector vs ArrayList
동구름이
동구름이
동구름이
동구름
동구름이
전체
오늘
어제
  • 분류 전체보기 (178)
    • Java (63)
      • Java 를 파헤쳐보자 (13)
      • BOJ (45)
      • 프로그래머스 (3)
      • SWEA (1)
      • Java GUI (1)
    • JavaScript (17)
      • JS를 파헤쳐보자 (7)
      • 프로그래머스 (7)
      • JS 학습 정리 (1)
    • Backend (33)
      • Spring (3)
      • HTTP (7)
      • 프로젝트 (10)
      • MySQL (6)
      • Redis (3)
      • Elastic Search (1)
      • 인증, 인가 (3)
    • CS (57)
      • 운영체제 (35)
      • Network (22)
    • Git (2)
    • 개발 관련 이것저것 (2)
    • etc (1)
    • 독서 (0)
    • 사설 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 프로그래머스
  • 이석복
  • Java
  • 구현
  • JCF
  • 백준
  • 스택
  • BOJ
  • 한양대
  • 네트워크
  • 레디스
  • 큐
  • OS
  • 김영한
  • 자바스크립트
  • 자바
  • 운영체제
  • 인프런
  • 모든 개발자를 위한 HTTP 웹 기본 지식
  • 반효경

최근 글

hELLO · Designed By 정상우.v4.2.2
동구름이
[Java 파헤쳐보기] java.util의 Arrays.sort()는 어떤 정렬 알고리즘을 사용할까?
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.