자바에서 정렬하는 방법

Arrays.sort()

원시타입의 배열을 정렬하는 Dual-Pivot QuickSort

💡

Dual-Pivot QuickSort 란?

QuickSort 에서 기준이 되는 Pivot 을 두 개로 나누어, 파티션을 총 3개로 분할하며 정렬하는 방식이다.

시간 복잡도 : O(n log n) 최악의 경우 O(n²)

pivot 의 기준점을 배열의 시작과 끝으로 지정하고, 두 개의 피벗의 값과 비교하며 배열을 총 3개의 파티션으로 나누는 것이 특징이다.

left side: left pivot 보다 값이 작은 파티션
center: left pivot 보다 크거나 같고, right pivot 보다는 작은 파티션
right side: right pivot 보다 큰 파티션

    private int[] sort(int[] A, int start, int end) {
        if (start < end) {
            // 두 pivot을 기준으로 분할
            int[] pivots = partition(A, start, end);
            
            // 3개 영역을 재귀적으로 정렬
            sort(A, start, pivots[0] - 1);      // 첫 번째 영역: < pivot1
            sort(A, pivots[0] + 1, pivots[1] - 1); // 두 번째 영역: pivot1 ~ pivot2
            sort(A, pivots[1] + 1, end);        // 세 번째 영역: > pivot2
        }
        return A;
    }

위 기준에 맞춰 재귀를 호출할 때 기존 QuickSort 는 왼쪽과 오른쪽 파티션에 대해서만 재귀를 호출했지만, Dual-Pivot QuickSort 는 세개의 파티션에 대해 재귀를 호출하게 된다.

왜 dual-pivot quick sort 일까?

우선, 일반적인 QuickSort 는 파티션이 한쪽으로 치우쳐지는 경우 O(n²) 시간 복잡도의 알고리즘이다. 한 개의 pivot 을 기준으로 파티셔닝 하다보니 발생할 수 있는 가능성이 현저히 낮지가 않다.

그렇기 때문에 파티셔닝이 한쪽으로 치우쳐지는 것을 방지하기 위해 파티션을 3개로 분할하여 각 파티션 별 데이터가 균형잡히도록 유도한다.

기존 one-pivot quick sort 보다 평균적으로 비교하는 횟수가 줄어들기 때문에 속도가 빠르다.

원시타입에서 배열은 데이터가 메모리에 연속된 공간에 저장되기 때문에 메모리 접근이 효율적이며 연산 속도가 빠른 장점이 있다.

반면, 객체는 생성시 힙 영역 에서 관리 되기 때문에 메모리 저장 위치가 분산되고, 객체간 비교를 위해 compareTo() 메서드를 호출해야하기 때문에 원시 타입에서 데이터를 바로 연산하는 것 보다 추가적인 오버헤드가 발생한다.

QuickSort 는 불안정 정렬로 정렬한 배열을 다른 기준으로 재정렬 하는 경우 순서는 무시된 채 모두 뒤죽박죽 뒤섞이게 되는 문제가 있다.

int[] scores = {95, 85, 95, 75};
Arrays.sort(scores);
// 결과: [75, 85, 95, 95]

원시 타입 배열에서 불안정 정렬을 사용해도 상관 없는 이유는 배열 내 데이터의 논리적인 의미를 두지 않기 때문이다.

반면, 객체라고 한다면 Student(90, "A"), Student(90, "C") 90점을 맞은 학생 A 와 C 에 있어 학생이라는 객체에서 논리적으로 이름이라는 속성이 의미를 갖고 있기 때문에 정렬 대상으로 두었을 때 불안정 정렬을 사용하면 뒤섞이게 된다.

Dual-Pivot QuickSort 내부에서 최적화된 다양한 정렬 방법

자바에서 원시타입 배열을 정렬하는 방식은 QuickSort 기반일 뿐 내부적으로는 아래 처럼 타입 별로 정렬하는 방식이 최적화 되어있다.

     static void sort(Sorter sorter, int[] a, int bits, int low, int high) {
        while (true) {
            int end = high - 1, size = high - low;

            /*
             * Run mixed insertion sort on small non-leftmost parts.
             */
            if (size < MAX_MIXED_INSERTION_SORT_SIZE + bits && (bits & 1) > 0) {
                mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high);
                return;
            }

            /*
             * Invoke insertion sort on small leftmost part.
             */
            if (size < MAX_INSERTION_SORT_SIZE) {
                insertionSort(a, low, high);
                return;
            }

            /*
             * Check if the whole array or large non-leftmost
             * parts are nearly sorted and then merge runs.
             */
            if ((bits == 0 || size > MIN_TRY_MERGE_SIZE && (bits & 1) > 0)
                    && tryMergeRuns(sorter, a, low, size)) {
                return;
            }

            /*
             * Switch to heap sort if execution
             * time is becoming quadratic.
             */
            if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
                heapSort(a, low, high);
                return;
            }

작은 크기의 배열은 삽입 정렬을 사용한다.
배열의 요소들이 대부분 정렬되어 있는 경우는 병합 정렬을 사용한다.
재귀 깊이가 깊어지는 경우 힙 정렬을 사용한다.

그 외적으로도 원시 타입의 종류에 따라 다른 정렬 방식을 사용하기도 하는데, 원시 타입이 표현할 수 있는 데이터 크기를 고려한 것 같다.

예를 들어 아래와 같이 byte, char, short 같은 경우 카운팅 정렬을 같이 사용하는 것을 볼 수 있다.

static void sort(byte[] a, int low, int high) {
    if (high - low > MIN_BYTE_COUNTING_SORT_SIZE) {
        countingSort(a, low, high);
    } else {
        insertionSort(a, low, high);
    }
}

static void sort(char[] a, int low, int high) {
    if (high - low > MIN_SHORT_OR_CHAR_COUNTING_SORT_SIZE) {
        countingSort(a, low, high);
    } else {
        sort(a, 0, low, high);
    }
}

static void sort(short[] a, int low, int high) {
    if (high - low > MIN_SHORT_OR_CHAR_COUNTING_SORT_SIZE) {
        countingSort(a, low, high);
    } else {
        sort(a, 0, low, high);
    }
}

참조타입을 정렬하는 TimSort

💡

팀 정렬이란?

2002년 팀 피터스에 의하여 현실 데이터들의 종류와 상관 없이 최적으로 정렬을 잘 수행하기 위한 알고리즘이 등장했다.

이 정렬 알고리즘은 삽입 정렬과 병합 정렬을 결합하여 만든 정렬로, 정렬을 위해 추가 메모리를 확보해야 하지만 O(n log n) 시간 복잡도를 자랑하는 다른 정렬 알고리즘의 단점을 최대한 극복하여 만든 알고리즘이다.

팀 정렬은 합병정렬을 기반으로 구현하되, 일정 크기 이하의 부분 리스트에 대해서는 이진 삽입 정렬을 수행하는 알고리즘이다.

팀 정렬은 기존 빠르다고 만들어진 알고리즘이 아닌 왜 병합정렬과 삽입정렬을 결합하여 만들었을까?

여타 빠르다는 알고리즘은 특정 상태에서 성능이 저하되는 알고리즘들인데, 이 상태에 불문하고 현실적인 데이터를 보편적으로 잘 정렬하기 위해 단점을 극복하였다고 생각된다.

O(n log n) 알고리즘 중

QuickSort: 매우 빠른 알고리즘이지만, 대부분 정렬된 상태일 때 O(n²) 로 성능이 저하된다.
HeapSort: 최선의 상황에서 굉장히 빠른 알고리즘이지만 참조 지역성을 만족하지 못하기 때문에 시간복잡도 이론 상 빠르다고 하더라도, 실제 QuickSort 참조 지역성으로 인해 보다 느린 경우도 있기 때문에 제외된다.
MergeSort: 인접한 덩어리를 병합하기 때문에 참조 지역성 원리를 만족하며, 안정 정렬이라는 점으로 채택된다.

팀 정렬에서 삽입 정렬은 이진 삽입 정렬로 최악의 경우 O(n²) 알고리즘이지만 배열이 이미 정렬 되어 있는 경우 O(n) 의 시간복잡도를 나타내며, 크기가 작은 배열에서는 O(n log n) 시간 복잡도를 나타내기도한다.

이진 삽입 정렬은 기존 삽입 정렬에서 비교해야 할 대상의 왼쪽으로 탐색하며 정렬하는 방식이었지만, 이진 탐색을 사용하여 O(n) 방식을 O(log n) 으로 줄인 알고리즘이다.

결론적으로 지역성이 높으면서, 추가적인 메모리를 최소화 하고, 시간복잡도가 O(NlogN) 이하의 알고리즘이 현실 데이터의 종류와 상관 없이 최적으로 정렬을 잘 수행할 수 있다는 것이다.

자바에서는 당연 원소타입 배열은 특정 타입으로 인해 데이터의 크기를 가늠할 수 있지만, 참조 타입은 객체의 크기를 알 수 없을 뿐더러 어떠한 종류가 올지 예상되지 않는다.

이로인해, 가장 보편적이면서 최적화된 알고리즘인 팀 정렬을 선택했다고 생각된다.

Collections.sort()

자바의 List 컬렉션에서 sort 메서드를 사용하면 내부적으로 Arrays.sort() 를 호출하여 결국 TimSort 알고리즘에 의해 정렬된다.

컬렉션을 통한 정렬 메서드를 사용할 때, 사용자가 직접 정의한 정렬 규칙을 같이 제공할 수 있으며, 아래 제공되는 함수형 인터페이스를 사용하는 람다식을 정의해야한다.

두 요소를 비교해서 o1이 더 작으면 음수, o1과 o2가 같으면 0, o1이 더 크면 양수를 반환하는 람다식을 정의해야한다.

o1 > o2 == 1 이면 오름차순 정렬이고, o1이 더 크니까 뒤로 이동한다.
o1 < o2 == -1 이면, 내림차순 정렬이다. o1이 더 작으니까 앞으로 이동한다.

Collections.sort(list, (o1, o2) -> o1.start>=o2.start?1:-1);

참고 자료

kyr-db.tistory.com

https://kyr-db.tistory.com/737

cladren123.tistory.com

https://cladren123.tistory.com/249

d2.naver.com

https://d2.naver.com/helloworld/0315536

geeksforgeeks.org

https://www.geeksforgeeks.org/dsa/timsort/