[Java] Arrays.sort()와 Collections.sort()의 시간복잡도 비교

[Java] Arrays.sort()와 Collections.sort()의 시간복잡도 비교

728x90

알고리즘을 풀다가 흔하디 흔한 sort() 정렬의 차이가 궁금해졌다.

보편적으로 배열을 정렬할 땐 Arrays.sort(), 컬렉션(List,Set..)을 정렬할 땐 Collections.sort()를 사용한다.

찾아보니 같은 sort 메서드지만 내부에서는 다른 정렬방식 을 사용하여 정렬한다고 한다. 이에 따라 시간복잡도도 달라 각 자료구조를 사용할 때 효율성 테스트의 성공/실패 결과가 달라질 수 있다. 이에 대한 내용을 간단히 정리해보자.

정렬 방식 시간 복잡도 Arrays.sort() DualPivotQuicksort 평균 : O(nlog(n)) / 최악 : O(n^2) Collections.sort() TimeSort (삽입정렬과 합병정렬을 결합한 정렬) 평균, 최악 : O(nlog(n))

따라서 최악이 O(nlog(n))의 시간복잡도를 갖고 있는 Collections의 sort()이 더 빠르며 평균 정렬 알고리즘으로 채택하여 사용하고 있다고 한다.

(특별한 제약이 없다면 무조건 Collections.sort()을 사용하기 보단 상황에 맞는 것을 사용하면 될 것 같다.)

참고

https://laugh4mile.tistory.com/175

728x90

from http://yuja-kong.tistory.com/183 by ccl(A) rewrite - 2021-11-20 20:28:24