<추천글>[JAVA] Tim Sort 알고리즘 / 지역성의 원리

정렬 알고리즘에서 시간복잡도의 핵심

- 정렬 알고리즘의 평균적인 시간복잡도는 C * nlg(n) + A이지만 (C는 상수) 여기서 C값을 결정하는 요인은 '지역성의 원리'이다.
- 지역성의 원리란 '최근에 참조된' 또는 '참조된 데이터의 주변의 데이터'가 또다시 참조될 가능성을 의미한다.
- 따라서 이를 활용하면 캐시 hit 발생률이 높아지고 메모리까지 가지 않아도 빠르게 데이터를 읽어올 수 있다.
- 예를 들어, merge sort의 경우에는 인접한 데이터들끼리 쪼개서 정렬 후 병합하기 때문에 지역성의 원리가 잘 활용된다고 볼 수 있다.
- 퀵 소트의 경우 pivot 주변에서 데이터의 이동이 빈번하게 발생하기 때문에 작은 C값을 가진다. (퀵 소트는 추가적인 메모리 사용 없이도 정렬한다는 점에서 '평균적으로' merge sort보다 성능이 좋다.)

 

cf. 퀵 소트가 정렬 알고리즘 중 가장 작은 C값을 가지기 때문에 다른 정렬 알고리즘에 비해 (평균적으로) 빠른 시간을 갖는다고 알려져 왔다. 즉, 퀵 소트는 하드웨어적으로 지역성의 원리가 가장 잘 적용된 알고리즘이라고 볼 수 있다.

 

Arrays.sort

Arrays.sort()는 기본적으로 듀얼피벗 퀵 정렬(Dual-Pivot QuickSort)을 수행한다. Dual-Pivot QuickSort는 피벗을 한 개 두는 일반적인 퀵 정렬과 다르게 피벗을 두 개 두고 3개의 구간을 만들어 퀵 정렬을 수행한다. 따라서 전체적인 성능(평균 시간복잡도)은 일반 퀵 정렬의 nlg(n)과 같지만 실질적으로는 일반 퀵 정렬보다 빠르다.

 

Collections.sort

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/List.html#sort(java.util.Comparator)

위 자바 11 공식 문서를 보면 Collections.sort 에서는 Tim Sort 알고리즘을 사용한다고 설명한다.

 

 

Tim Sort

- 기존의 정렬 알고리즘은 평균적으로 nlg(n)에 해결이 되었지만, 최악의 경우에는 O(n^2)이라는 단점이 있었다.
- 이러한 단점으로인해 최악의 경우에도 효율적인 정렬 알고리즘을 고안하고자 등장했다.
- insertion sort와 merge sort가 결합된 정렬 알고리즘이다. 평균 시간복잡도 nlg(n)을 가지며 빅-오 또한 O(nlg(n))이다.
- Insertion sort는 인접한 메모리와의 비교를 반복하기 때문에 지역성의 원리가 잘 활용되는 정렬 알고리즘이다.
- 즉, 전체를 작은 덩어리로 잘라 각 덩어리를 insertion sort로 정렬한 뒤 병합하는 방식을 활용하는 것이 기본적인 Tim sort의 원리이다.
- insert sort는 O(n^2)의 성능을 갖지만 binary insert sort를 도입하여 삽입할 위치를 찾을 때 이분탐색을 이용하는 방식을 취한다. 지역성의 원리는 약간 떨어질 수 있지만 O(logn)의 성능을 보장한다. 따라서 Time sort의 성능이 O(nlg(n))을 갖는 것이다.

 

Reference

- https://d2.naver.com/helloworld/0315536