[JAVA] 정렬에 대한 고찰 (Arrays.sort() 와 Collections.sort())

최근 백준 - 수 정렬하기 2 라는 문제를 풀다가 이상한 상황을 겪었다.

Link : https://www.acmicpc.net/problem/2751

아니 배열에 담아 Arrays.sort() 해서 출력하면 시간초과가 나고 ArrayList에 담아 Collections.sort()를 하니까 통과되는 것이다!!! 덕분에 새로운 사실을 알게 되었다.

 

바로 Java에서 제공해주는 API 중 Arrays.sort() 와 Collections.sort() 가 서로 다른 정렬 알고리즘으로 구현되어있다는 것이다.

 

Arrays.sort() : DualPivotQuicksort

Arrays.sort()의 메서드를 클릭했을 때를 보면

다음과 같이 나온다. 저 DualPivotQuicksort를 클릭하니 4000라인의 코드가 나를 반겼다. 황급히 뒤로가기를 눌렀다.

글을 읽어 보니 Arrays.sort()는 듀얼 피봇 퀵정렬을 채택했고 블라디미르 뭐시기랑 존 벤틀리, 조슈아 세명이서 만든것 같다. 듀얼 피봇 퀵소트는 평균 O(nlog(n))의 시간복잡도를 가지며 최악의 경우 O(n^2)이 될 수 있다.

 

 

Collections.sort() : Timsort

IDE에서 Collections.sort()를 클릭하면 너무 복잡한 내용이 즐비하다. 그래도 내용을 정리하면 Collections.sort()는 Timsort()라는 정렬기법을 사용한다는 점이다.

여기서 Timsort란 삽입 정렬과 합병정렬을 결합하여 만든 정렬이라고한다. Timsort의 시간복잡도는 평균 O(n log(n)) 이며 최악의 경우도 O(n log(n)) 이다. 삽입정렬의 평균 시간 복잡도가 O(n^2) 인데 어떻게 그런 수치가 나오지? 라고 궁금증을 느껴 정리된 글을 찾아 봤다. 

여기 정말 자세하게 설명해주신 분의 글이 있다. Link : https://d2.naver.com/helloworld/0315536

으음..

아직 내 실력이 너무 미천하여 백프로 이해 하기엔 무리가 있지만 시간 복잡도가 같아도 참조 지역성의 원리를 얼마나 잘 만족하느냐에 따라서 상수값이 차이가 나고, 그 상수값이 생각보다 유의미한 값이여서 성능의 차이가 나는것으로 이해했다. Timsort는 그 상수값을 최대한 줄이기위해 갖가지 최적화 기법을 기용한 알고리즘이다.

결론적으로, 최악의 시간복잡도가 O(n log(n))라는 다소 안정적인 수치로 인해 많은 표준 정렬 알고리즘으로 채택하여 사용하고 있다고 한다.