Arrays.sort와 Collections.sort의 효율차이 (+ Tim sort란?)

SionBackEnd·2022년 7월 15일
0

CS

목록 보기
1/9
post-thumbnail

알고리즘 관점에서 보는 효율차이

Arrays.sort()

Arrays.sort()는 배열을 정렬할때 자주 사용하는 방식이다. 디폴트값으로는 오름차순을 지원해준다.
Arrays.sort()는 듀얼 피봇 퀵정렬을 채택했다.

시간 복잡도

듀얼 피봇 퀵소트는 평균 O(nlog(n))의 시간복작도를 가지고 최악의 경우에는 O(N^2)이 될수있다. 한마디로 많이 느려질수있다...

Collections.sort()

Collections.sort()는 컬렉션을 정렬할때 자주 사용하는 방식이다. 디폴트 값으로는 오름차순을 지원해준다.
Collections.sort()는 Timsort()라는 기법을 사용한다. Timsort란 삽입 정렬과 합병정렬을 결합하여 만든 정렬이라고 하는데 너무 깊게 들어가는건 다음에 공부해보자.

시간복잡도

TImsort의 시간복잡도는 평균 O(nlog(n))이고 최악의 경우도 O(nlog(n))이다. 최악의 시간복잡도가 O(n log(n))라서 다소 안정적인 수치로 인해 많은 표준 정렬 알고리즘으로 채택하여 사용한다고 한다.

정렬에 관한 포스팅

Tim sort에 대해 알아보자

profile
많은 도움 얻어가시길 바랍니다!

0개의 댓글