[JAVA] Collections.sort vs Arrays.sort 차이

자바를 다루다보면 데이터를 오름차순, 또는 내림차순으로 가공해야 하는 경우가 생긴다. 이때에는 직접 정렬시키는 방법도 있겠으나, 보통은 자바 클래스 라이브러리에서 제공하는 메서드를 사용한다.  대표적으로 배열을 정렬해주는 Arrays.sort()와 객체를 정렬해주는 Collections.sort().

 

 

표면적으로 보면 정렬 대상이 배열이면 Arrays을 사용하고, 정렬 대상이 그 외 리스트와 같은 객체이면 Collections을 사용하면 될 것 같지만, 백준 문제풀이와 같이 출제자가 의도적으로 산출 시간에 제한을 걸어둔 경우 두 경우의 시간 복잡도나 공간 복잡도를 고려하여 어떤 방법을 사용할지 선택해야 할 때가 있다.

 

따라서 이번 기회에 두 정렬 방법에 대한 차이점을 정리해둘까 한다. 

 

 

 

 

Arrays 와 Collections

	정렬 방식	시간 복잡도
Arrays.sort()	DualPivotQuicksort	평균 : O(NlogN) / 최악 : O(N^2)
Collections.sort()	TimeSort (insert & merge)	평균, 최악 : O(NlogN)

 

Arrays.sort()의 경우 일반 듀얼 피봇 퀵정렬을 사용하는데, 일반 퀵정렬과 다르게 피봇 2개로 나눈 3개의 구간을 만들어 진행한다. 이 경우 랜덤 데이터에 대해서 평균적으로 퀵정렬보다 나은 성능을 보인다고 알려져 있다. 

Collections.sort()의 경우에는 삽입 정렬과 합병 정렬을 결합하여 만든 Tim 정렬을 사용한다. 

 

 

 

Arrays.sort 와 Collections.sort에 사용되는 정렬 방식이 다른 이유는 배열과 리스트 자료구조의 차이점때문이다. 

정렬의 실제 동작 시간은 C * 시간 복잡도 + a 이다. a는 상대적으로 무시할만한 정도이고 실질적으로 동작 시간에 영향을 미치는 요인은 C(Cache Hit Rate의 역수?)과 시간복잡도이다. 

Cache Hit Rate에 대한 설명은 아래 글 참고.

[JAVA] Array vs ArrayList vs LinkedList

 

 

 

C의 값은 Cache Hit Rate이 높을 수록 낮은 값을 갖는다. 따라서 데이터들이 메모리상에 연속적으로 저장되어있는 배열의 경우 C의 값이 더 낮다. 반면 리스트의 경우 배열과 비슷한 형태의 ArrayList뿐만 아니라 메모리 상에 산발적으로 데이터가 저장되어 있는 LinkedList도 존재한다. 

따라서 Arrays.sort의 경우 참조 지역성이 좋은 퀵 정렬을 사용하고, Collections.sort의 경우 퀵 정렬보다는 합병정렬과 삽입정렬을 결합하여 만든 Tim 정렬을 사용하는게 평균적으로 더 좋은 성능을 기대할 수 있게 한다.

 

 

 

 

 

 

 

 

 

참고

[Java] Java의 정렬 알고리즘 - Arrays와 Collections