목표

• Arrays.sort()의 구현을 이해한다.

Arrays.sort() 구현체

일반 정렬

public static void sort(int[] a)

• Dual-Pivot Quick Sort
• 1 피벗 Quick sort에 비해 많은 데이터 셋에서 O(n log n)의 빠른 속도를 보장

객체 정렬

public static void sort(Object[] a)

• Comparable T 인터페이스를 구현해야 함
• Comparable 구현을 통해 Natural Ordering 문자열 정렬
  a1, a10, a2, a 20 -> a1, a2, a10, a20 문자열에 속한 숫자를 말그대로 자연스러운 방식으로 정렬
• ASC, DESC 정렬 지원
• Stable(안정적) 정렬
  데이터의 상대적 순서가 유지 됨
• 반복 병합 정렬로 Tim sort를 사용, 무작위 정렬 시에도 Merge sort의 시간복잡도를 보장
  정말 잘 되어 있는 Naver D2 Tim sort 설명

함수의 사용

public static void main(String[] args) { // 0.009 Dual-Pivot Quick
        Random random = new Random(System.nanoTime());
        int[] arr = new int[50000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(50000);
            for (int j = 0; j < i; j++) {
                if (arr[i] == arr[j]) {
                    i--;
                }
            }
        }
        long start, end;
        start = System.currentTimeMillis();
        Arrays.sort(arr);
        end = System.currentTimeMillis();
        System.out.println((end - start) / 1000.0);
    }

• Dual-Piovt Quick sort를 이용한 정렬
  데이터 5만개 0.009초

public static void main(String[] args) { // 0.021초 Tim sort
        Random random = new Random(System.nanoTime());
        Integer[] arr = new Integer[50000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(50000);
            for (int j = 0; j < i; j++) {
                if (arr[i].equals(arr[j])) {
                    i--;
                }
            }
        }
        long start, end;
        start = System.currentTimeMillis();
        Arrays.sort(arr);
        end = System.currentTimeMillis();
        System.out.println((end - start) / 1000.0);
    }

• Tim sort를 이용한 Integer 객체 정렬
  데이터 5만개 0.021초
• n개의 데이터로 줄어들 때 까지 Merge sort로 동작하고 n개에 대해서는 Insertion sort로 동작

결론

Java Collection Framework에 속한 Arrays.sort()의 구현체에 대해서 알아보았다.
Merge sort는 O(n log n)의 속도를 가진다고 알려져 있지만 실제로 그보다 느려 대부분 Quick sort를 사용하고 있다.
하지만 JDK에서는 기본 정렬 알고리즘으로 Merge sort + Insertion sort인 Tim sort를 택했고 그에 대해서도 알게되었다.
정렬 알고리즘들은 실제로 구현할 일은 별로 없지만 왜 그런 알고리즘들을 택했는지에 대해서는 알 수 있다.

참고

Naver D2 Tim sort에 대해 알아보자
Java SE9 & JDK9