Algorithm - Tim Sort

Tim Sort에 대해서 알아봅니다.

 

GOAL

• Tim Sort의 원리를 이해한다.

 

정렬 알고리즘

정렬은 프로그래밍을 배울 때 기초적인 알고리즘으로 자주 소개되곤 한다. 일반적으로 정렬이 갖는 시간 복잡도는 O(n logN)이라고 알고있고, 버블, 삽입, 퀵 등 다양한 정렬 알고리즘이 있는데, 실제로 내가 사용하는 언어에서는 어떻게 구현되어있을까?

대표적인 정렬 알고리즘들

잘 알려진 정렬 알고리즘들을 비교한 표이다. 이 비교만 본다면 Heap Sort가 제일 성능이 좋은데, 이걸 사용하면 될 것 같다. 하지만 여기엔 빅오 표기법의 한계가 드러난다.

 

빅오 표기법

빅오 표기법은 부가적으로 붙는 상수항을 제거하고 비교한다. "입력 크기 n이 커질 때 알고리즘의 실행 시간이 얼마나 빨리 증가하는지"만 비교하기 때문이다.

 

평균 시간 복잡도가 O(n logN)인 Heap, Merge, Quick 정렬을 좀 더 상세하게 살펴보자.

빅오 표기법의O(n logN)은 실제로 C x n logN + a 라는 의미이다. 상대적으로 무시할 수 있는 부분인 a를 제외하면 C라는 상수가 곱해져 있어, 이 값에 따라 실질적인 시간에 큰 차이가 생긴다. 여기서 C값에 큰 영향을 끼치는 요소로 "참조 지역성(Locality of Reference)"가 있다.

 

* 참조 지역성이란?

CPU가 미래에 원하는 데이터를 예측하여 속도가 빠른 장치인 캐시 메모리에 담아 놓는데 이때의 예측률을 높이기 위하여 사용하는 원리이다. 쉽게 말하자면, 최근에 참조한 메모리나 그 메모리와 인접한 메모리를 다시 참조할 확률이 높다는 이론을 기반으로 캐시 메모리에 담아놓는 것이다. 메모리를 연속으로 읽는 작업은 캐시 메모리에서 읽어오기에 빠른 반면, 무작위로 읽는 작업은 메인 메모리에서 읽어오기에 속도의 차이가 있다.

 

그러면 이제 참조 지역성의 개념과 함께 세 정렬 알고리즘을 다시 비교해보자.

1. Heap Sort

대표적으로 참조 지역성이 좋지 않은 알고리즘이다. 한 위치에 있는 요소를 해당 요소의 인덱스 두 배 혹은 절반의 요소과 반복적으로 비교하기에 캐시 메모리에서 예측하기 매우 어렵다.

 

2. Merge Sort

인접한 덩어리를 병합하기에 참조 지역성을 어느 정도 잘 만족한다. 하지만 입력 배열 크기만큼의 메모리를 추가로 사용한다는 단점이 존재한다.

 

3. Quick Sort

pivot 주변에서 데이터의 위치 이동이 빈번하게 발생하기 때문에 참조 지역성이 좋으며 메모리를 추가로 사용하지 않는다. 실제로 Quick Sort의 C는 다른 두 정렬보다 작은 값으로 정의되어 있으며, 평균 시간 복잡도는 다른 비교군 두 정렬 알고리즘에 비해 가장 빠르다고 알려져 있다. 하지만 pivot을 선정하는 방법에 따라 최악의 경우 O(n^2)까지 시간 복잡도가 나빠질 수 있다는 단점이 존재한다.

 

 

Tim Sort

2002년 소프트웨어 엔지니어 Tim Peters에 의하여 Tim sort가 등장했다. 이 정렬 알고리즘은 Insertion sort와 Merge sort를 결합하여 만든 정렬이다.

 

실생활 데이터의 특성을 고려하여 설계된 이 알고리즘은 최선의 시간 복잡도는 O(n), 평균/최악의 경우에도 O(n logN)을 갖는다. 또한 안정 정렬을 결합했기에 안정 정렬로 동작하며, 추가 메모리는 사용하지만 Merge Sort에 비해 적은 추가 메모리를 사용하여 위에 비교했던 다른 정렬 알고리즘들의 단점을 최대한 극복한 정렬 알고리즘이다. 현재 java, python, V8 등의 언어에서 Tim Sort를 사용하는 것을 확인할 수 있다.

 

기본 원리

위에서 설명한 것과 같이 Insertion Sort와 Merge Sort를 결합하여 만들어진 정렬 알고리즘이다. Merge Sort는 평균 시간 복잡도가 O(n logN)이니 그렇다 쳐도 평균 시간 복잡도가 O(n^2)인 Insertion Sort는 왜 결합했을까? 여기서 아까 언급했던 참조 지역성이 핵심적인 내용이다.

 

Insertion Sort는 인접한 메모리와의 비교를 반복하기에 참조 지역성의 원리를 매우 잘 만족한다. 이에 따라 Insertion sort의 상수 C를 Ci​, O(nlogn) 정렬 알고리즘 중 C 값이 가장 작다고 알려져 있는 Quick sort의 상수 C를 Cq라 할 때, 작은 n에 대하여 Ci * n^2 < Cq * n log⁡N이 성립한다. 즉, 작은 n에 대하여 Insertion sort가 빠르다는 것이다.

이런 아이디어를 이용해서 전체를 작은 덩어리로 잘라 각 덩어리를 Insertion Sort로 정렬한 뒤 Merge Sort로 병합하면 더 빠르다는 것이 기본적인 원리이다.

 

2^x개로 잘라 각각을 Insertion Sort로 정렬하면 일반적인 Merge Sort보다 덩어리별 x개의 병합 동작이 생략되어 Merge Sort의 동작 시간을 Cm * n logN이라고 할 때, Tim Sort의 동작 시간은 Ci * n(logN - x) + a가 된다. 여기서 더욱 최적화하기 위해 x의 값을 크게 하고 a의 값을 줄이는 여러 기법들도 존재한다. 실질적은 최적화 기법들은 아래 네이버 D2에서 상세하게 소개되어있으니 확인해보는 것도 좋을 것 같다.

 

* 왜 2^x개로 잘라 각각을 Insertion Sort로 정렬하면 덩어리별 x개의 병합 동작이 생략될까?

Merge Sort의 핵심 비용은 “깊이 수 × 각 깊이의 N 처리”이다. 보통은 한 개부터 시작해 2개씩 이어 붙이므로 logN의 깊이를 가지게 되고, 각 깊이마다 n을 훑기 때문에 n logN이 되는 것이다. 하지만 여기서 한 개부터 시작하는 것이 아니라 2^x개로 시작하여 적은 크기를 Insertion Sort로 병합하면 x깊이까지는 병합 동작이 생략되게 된다.

 

참고

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