[JAVA] Arrays.sort Collections.sort 알고리즘 차이

 

/* Arrays.sort, Collections.sort */

Arrays.sort() 는 Array를 정렬해준다.

Collections.sort()는 ArrayList, LinkedList 같은 List 인터페이스를 정렬해준다.

 

/* Arrays.sort */

• primitive 타입인 경우 

 

Arrays.sort() 를 살펴보니 듀얼피봇 퀵정렬(Dual-Pivot Quicksort)을 사용한다고 되어 있다. 

Dual-Pivot Quicksort는 Quicksort와는 다르게 Pivot을 2개를 두고 3개의 구간으로 만들어 Quicksort를 진행한다고 한다.

이 때 Pivot을 설정할 때는 Median을 이용한다고 알고 있다. 

시간복잡도는 O(n log(n))으로 나와있다.

• reference(참조) 타입인 경우 (객체 클래스)

 

참조 타입인 경우는 TimSort를 사용한다고 나와있다.

Timsort는 InsertionSort와 MergeSort 를 섞은 정렬 방법이라고 한다.

/* Collections.sort */

 

 

Collections.sort() 를 보면 list.sort()의 메서드를 실행한다.

 

 

list.sort() 메서드를 보면 Arrays.sort()를 실행한다는 것을 알수가 있다.

위에서 살펴봤듯이 이는 곧 Array.sort()를 실행할 때 TimSort가 사용되는 것을 알 수가 있다.

이때 시간 복잡도는 O(n log(n))이라고 한다.