[Java] 자바 내장 정렬 함수 - Arrays.sort()

데이터들을 정렬시킬 때, 어떤 정렬 알고리즘을 사용해야 하는지 판단하는 중요한 요소중 하나는 시간 복잡도입니다.

자바 내부에서 사용하는 정렬은 시간 복잡도가 얼마인지 알 필요성이 있다고 생각합니다.

이번 포스팅에서는 자바의 내장 정렬 함수 중 하나인 Arrays.sort()를 알아보도록 하겠습니다.(JAVA 8 기준)

 

java.util.Arrays.sort()

 

Arrays.sort()는 내부적으로 DualPivotQuicksort.sort()를 호출한다.

퀵 정렬의 시간 복잡도는 일반적으로 최선의 경우에는 O(nlogn)을 가지고, 최악의 경우에는 O(n^2)를 가진다.

주석을 해석해보면 DualPivotQuicksort.sort()는 최악의 시간 복잡도를 갖게 하는 많은 데이터 셋들에 대해서도 O(nlogn)의 시간 복잡도를 제공하고, 일반적인 (one-pivot) 퀵 정렬보다 좋은 성능을 가진다고 한다. 

일반적인 퀵 정렬보다 pivot을 하나 더 사용함으로써 조금 더 좋은 성능을 가지는 거 같다.

 

 

DualPivotQuicksort의 내부 전역 변수이다. 주석들을 해석해보면 각각 배열의 크기에 따라 

MergeSort, QuickSort, InsertionSort, CountingSort가 사용된다. 

• MergeSort의 최대 실행 수는 67이다.
• MergeSort의 최대 길이는 33이다.
• 배열의 길이가 286보다 작을 경우 MergeSort보다 QuickSort가 우선적으로 사용된다.
• 배열의 길이가 47보다 작을 경우 QuickSort보다 InsertionSort가 우선적으로 사용된다.
• byte타입 배열의 길이가 29보다 큰 경우 InsertionSort보다 CountingSort가 우선적으로 사용된다.
• short, char타입 배열의 길이가 3200보다 큰 경우 QuickSort보다 CountingSort가 우선적으로 사용된다.

배열의 크기에 따라 정렬 알고리즘을 나누는 이유는 CountingSort는 데이터의 값이 몇 번 나왔는지 카운팅 하는 새로운 배열을 만들고, MergeSort는 데이터를 합병(Merge) 하기 위한 새로운 배열을 만든다. 가령 크기가 3인 배열을 정렬하기 위해 새로운 배열을 만드는 것은 비효율적이기 때문에 배열의 크기에 따라 정렬 알고리즘을 나누는 것이다.

 

 

전역 변수 밑으로 다양한 알고리즘이 구현되어 있고 퀵 정렬을 살펴보면 일반적은 퀵 정렬과 다르게 두 개의 pivot을 사용하는 것을 살펴볼 수 있다. 때문에 DualPivotQuicksort라고 부른다.

 

결론적으로 Arrays.sort()는 내부적으로 O(n)의 시간 복잡도부터 O(nlogn), O(n^2)까지 다양하게 발생할 수 있기 때문에 상황에 따라서 적절하게 사용되어야 한다.