Java의 Arrays.sort()를 사용할 때 원시형 타입이 아닌 참조형 타입으로 전달하면 성능 향상이 가능하다 (Dual-Pivot Quicksort, Tim Sort)

Arrays.sort()를 사용할 때 원시형 타입이 아닌 참조형 타입으로 전달하면 성능 향상이 가능하다.

 

그 전에 먼저 sort() 메서드에 대해 간단히 살펴보자. 

 

아래와 같이 다양한 sort() 메서드가 오버로딩 되어 있다.  

 

public class Arrays {

    
    private Arrays() {}

    public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, 0, a.length);
    }

    public static void sort(int[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
        DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
    }

    public static void sort(long[] a) {
        DualPivotQuicksort.sort(a, 0, 0, a.length);
    }

   
    public static void sort(long[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
        DualPivotQuicksort.sort(a, 0, fromIndex, toIndex);
    }

    
    public static void sort(short[] a) {
        DualPivotQuicksort.sort(a, 0, a.length);
    }

   
    public static void sort(short[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
        DualPivotQuicksort.sort(a, fromIndex, toIndex);
    }

.
.
.
.
}

 

- void sort(int[] a): 정수형 배열을 오름차순으로 정렬한다. 

- void sort(int[] a, int fromIndex, int toIndex): 지정된 범위 내의 정수형 배열 요소를 오름차순으로 정렬한다. 

- void sort(Object[] a): 객체 배열을 오름차순으로 정렬한다. 이때, 배열의 요소는 Comparable 인터페이스를 구현해야 한다.

- void sort(Object[] a, int fromIndex, int toIndex): 지정된 범위 내의 객체 배열 요소를 오름차순으로 정렬한다. 

- void sort(T[] a, Comparator<? super T> c): 객체 배열을 주어진 Comparator 객체를 사용하여 정렬한다. Comparator 객체를 통해 정렬 기준을 지정할 수 있다.

 

 

 

정렬 방식 

 

Arrays.sort()는 원시형 타입의 인자에 대해서는 Dual-Pivot Quicksort 를 사용한 방식으로 정렬 기능을 수행하며, 참조형 타입에 대해서는 Tim Sort라는 정렬 방식을 갖는다. 

 

퀵 정렬을 개선한 Dual-Pivot Quicksort은 퀵정렬과 마찬가지로 평균/최선일 때 O(nlogn), 최악일 때 O(n^2)의 시간 복잡도를 가지며, Tim Sort는 평균/최선/최악의 경우 모두 O(nlogn)을 갖는다. 

 

 

1) Dual-Pivot Quicksort

 

/**
 * Sorts the specified array into ascending numerical order.
 *
 * @implNote The sorting algorithm is a Dual-Pivot Quicksort
 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 * offers O(n log(n)) performance on all data sets, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * @param a the array to be sorted
 */
public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, 0, a.length);
}

 

 

퀵 정렬은 분할 정복 방식 (Divide and conquer) 으로 정렬을 수행하며 평균적으로 시간 복잡도 O(NlogN)을 가진다. 최악의 경우 O(n^2)으로 단순 정렬과 다를 바가 없지만, pivot을 조정하는 것만으로도 악조건을 쉽게 피할 수 있기 때문에 널리 사용되는 효율적인 알고리즘으로 알려져있다.

 

그러다면 Arrays.sort()에서 제공하는 Dual-Pivot Quicksort 이란 무엇일까? implNote에 따르면 전통적인 1 pivot 방식의 퀵정렬보다 빠르다고 설명하고 있다. 

 

Dual-Pivot Quicksort 방식은 분할 단계에서 배열을 두 개의 피벗을 기준으로 분할하여 작은 값과 큰 값의 영역을 동시에 만들어낸다. 이로 인해 분할이 더욱 효율적으로 이루어질 수 있다. 즉, 단일 피벗 방식에서 발생할 수 있는 불균현한 분할 문제점을 사전에 방지하도록 하여 최악의 시간 복잡도를 피하는 것이다.

 

다음과 같은 이점을 갖는다. 

i) 비교 횟수의 감소: Dual-Pivot Quicksort는 단일 피벗 방식에 비해 비교 횟수를 줄일 수 있다. 이는 배열을 두 개의 피벗(pivot)으로 분할하여 정렬하는 방식으로, 한 번의 분할로 배열을 세 영역으로 나눌 수 있다. 따라서 평균적으로 비교 횟수가 줄어든다

 

ii) 스왑 작업 감소: Dual-Pivot Quicksort는 단일 피벗 방식보다 스왑 작업을 더 적게 필요로 한다. 이는 두 개의 피벗과 세 영역으로 분할되어 정렬되기 때문에 스왑 작업이 더욱 효율적으로 이루어질 수 있다.

 

 

결과적으로 정렬된 배열이나 중복된 요소가 많은 배열과 같은 특수한 입력에 대해서도 일반적인 퀵소트 알고리즘보다 더 나은 성능을 보인다. 

 

그런데 복잡도 면에서 이보다도 더 좋은 성능을 보이는 것이 바로 Tim Sort이다.

 

 

2) Tim Sort 

 

 

 

Arrays.sort()는 Object Type에 대해서는 Tim Sort를 수행한다. 

 

Tim Sort의 특징은 노트에서도 이야기하듯이 안정적 정렬(stable)이라는 점이다. 동일한 값에 대해서도 원래 순서를 유지하는 안정적인 정렬 알고리즘이다. 따라서 동일한 값에 대한 상대적인 순서가 중요한 경우에 유용하다.

 

Tim Sort는 기본적으로 merge 정렬 메커니즘으로 작동한다고 한다. 작은 크기의 배열부터 시작하여 부분적으로 정렬하고, 이 정렬된 부분들을 병합하는 방식으로 동작한다. 

 

어쨌든, stable이 보장되고 최악의 경우에도 O(nlogn)의 시간복잡도를 갖고 있다는 점이 큰 장점이다. 

 

따라서 Arrays.sort()를 사용한 정렬이 필요한 상황에서 큰 비용이 드는 것이 아니라면 원시값을 참조형으로 바꾼 배열로 전달해주는 것만으로도 큰 성능 향상을 기대할 수 있는 부분이 있을 것이다.