자바의 정렬에는 두 종류가 있다.
가끔 알고리즘 문제를 풀다 보면 Arrays.sort()를 사용했을 때는 틀렸지만 Collections.sort()를 사용하면 성공하는 경우가 있다. 같은 정렬 알고리즘이지만 시간 차이가 나는 이유는 무엇일까?
정렬 알고리즘
정렬 알고리즘에서 흔히 가장 빠르다고 알려진 알고리즘은 퀵 소트와 머지 소트이다. 둘 다 O(nlogn)의 시간 복잡도를 가지기 때문이다.
하지만 퀵 소트는 워스트 케이스가 O(n^2)이기 때문에 특정 경우 머지 소트보다 오래걸리는 경우가 발생한다.
자바도 이런 경우 때문에 두 정렬 API에 차이가 발생한 것은 아닌지 알아 보았다.
Arrays.sort()
사진에서 볼 수 있듯이 Arrays.sort()는 DualPivotQuicksort를 사용하고 있다.
퀵소트는 피봇을 하나 사용하는데 자바에서는 피봇을 2개 사용하는 형태로 구현되어 있다. 하지만 퀵 소트이기때문에 시간복잡도는 최악의 경우 O(n^2)이 될 것이다.
Collections.sort()
반대로 Collections.sort()는 머지 소트와 팀 소트를 같이 사용하고 있다. 팀 소트는 머지 소트와 삽입 정렬의 장점을 가져와 합친 정렬로 대부분의 언어에서 정렬 알고리즘으로 채택하고 있다. 따라서 둘 모두 최악의 경우 시간복잡도가 O(nlogn)이다.
Why??
그렇다면 자바는 왜 정렬을 2가지 방법으로 구현해놓았을까?
이유는 Array 같은 경우 메모리적으로 연속적인 주소를 가지고 있기 때문에 참조 지역성이 높다. 따라서 퀵 정렬과 같이 참조 지역성이 좋은 정렬 알고리즘은 충분히 좋은 성능을 제공할 수 있다.
하지만 Collection은 List를 예로 볼 때 ArrayList도 있지만 참조 지역성이 좋지않은 LinkedList도 있다. 따라서 참조 지역성이 좋지 않아 퀵 정렬로 할 경우 시간 복잡도가 높아질 위험이 있다. 그래서 Tim 소트를 이용하는게 평균적으로 더 좋은 성능을 기대할 수 있다.
참조
