[알고리즘] Arrays.sort()와 Collections.sort()의 시간복잡도 비교

Arrays.sort()와 Collections.sort()

알고리즘 정렬 문제를 풀던 중 Arrays.sort()와 Collections.sort()의 시간복잡도에 차이가 있다는 점을 깨닫게 되었다. 같은 sort() 메서드지만 내부에서는 다른 정렬법을 사용한다.

	정렬 방식	시간 복잡도
Arrays.sort()	Dual-Pivot QuickSort	평균 : O(n log n) / 최악 : O(n^2)
Collections.sort()	TimSort (삽입정렬과 합볍정렬을 결합한 정렬)	평균, 최악 : O(n log n)

 

Arrays.sort()의 경우 Dual-Pivot QuickSort 알고리즘을 사용한다. 평균 시간복잡도가 O(n log n)이고 매우 빠른 알고리즘인 것은 맞다. 하지만 최악의 경우 시간복잡도는 O(n^2)이라는 점을 인지해야 한다.

 

Collections.sort()은 TimSort 이다. TimSort의 경우 합병 및 삽입정렬 알고리즘을 사용한다. 이렇게 두 가지가 섞여있는 정렬 알고리즘을 hybrid sorting algorithm이라고 하는데. 합병정렬 (Merge Sort)의 경우 최선, 최악 모두 O(n log n)을 보장하고, 삽입정렬 (Insertion Sort)의 경우 최선의 경우는 O(n), 최악의 경우는 O(n^2)이다. 그리고 두 정렬 모두 안정 정렬(Stable Sort)이기 때문에 TimSort를 hybrid stable sorting algorithm이라고도 한다.

 

언제, 무엇을 사용해야 할까?

Arrays.sort는 기본형 배열을 정렬할 때 Dual-Pivot QuickSort를 사용하여 빠른 성공을 제공하며, 객체 배열 및 컬렉션을 정렬할 때는 TimSort를 사용하여 안정적인 성능을 제공한다. 반면, Collections.sort()는 List 인터페이스를 구현한 컬렉션을 정렬할 때 Arrays.sort()를 호출하여 TimSort 알고리즘을 사용한다.

 

종합적으로, 배열을 정렬할 때는 Arrays.sort()를, 컬렉션을 정렬할 때는 Collections.sort()를 사용하는 것이 좋은 방법인 것 같다. 두 메서드는 모두 효율적인 정렬을 제공하지만, 사용되는 데이터 타입과 상황에 따라 적절한 메서드를 선택하는 것이 중요하겠다!