[python] 파이썬의 정렬, Tim Sort

Tim Sort

python에서의 정렬 함수 sorted()와 list.sort()에 사용된 정렬 알고리즘은 Timsort, 팀정렬입니다.

팀정렬은 파이썬 핵심 개발자인 팀 피터스에 의해서 Cpython에서 처음으로 구현되었으며 2009년 이후 표준 자바 및 안드로이드, swift 등 여러 언어에서 사용되고 있습니다.

이는 데이터의 정렬된 정도에 따라 삽입정렬과 병합정렬 사이를 전환하는 적응형 알고리즘입니다. 두 정렬방법을 결합했기에 안정적이며, 추가 메모리는 사용하지만 기존의 병합정렬에 비해 적은 추가메모리를 사용하여 다른 O(nlogn) 정렬 알고리즘의 단점을 최대한 극복한 알고리즘입니다.

 

알고리즘의 원리

위에서 언급했듯이 팀정렬은 삽입정렬과 병합정렬을 함께 사용하고 있습니다.

병합정렬은 추가적인 메모리를 필요로 하지만 퀵정렬과 함께 굉장히 빠른 정렬 방법으로 알려져 있지만 삽입정렬은 그렇지 않습니다.

삽입정렬의 평균 복잡도는 O(n^2)으로 O(nlogn)의 다른 정렬 알고리즘보다 성능이 떨어진다고 알고 있습니다.

n^2와 nlogn은 n의 값이 굉장히 커질 때 영향을 많이 받게 되지만 n의 값이 적당히 작을 때는 앞의 상수에 의해서 바뀔 수 있습니다.

실제로 적당히 작은 n에 대해서 삽입정렬이 퀵정렬보다 빠른 속도를 보여줍니다.

이로부터 병합정렬로 데이터를 나눈 후 각각에 대해 삽입정렬을 통해 정렬 시간을 줄일려는 생각을 하였고 팀정렬이 나오게 되었습니다.

병합정렬의 소요시간이 C*nlogn 이라고 한다면 팀정렬은 C*n(logn-x)+a 로 x값과 a값을 조정함으로서 튜닝할 수 있습니다.

 

Binary Insertion Sort

팀정렬에 대해 본격적으로 알아보기 전에 삽입정렬에 대해 짚고 넘어가겠습니다.

기존의 삽입정렬은 삽입할 적절한 위치를 찾을 때까지 하나씩 비교를 하지만 팀정렬에서 사용하는 이진삽입정렬은 이분탐색을 통해서 적절한 위치를 찾게 됩니다.

이 방법은 시간복잡도는 개선되지만 참조지역성을 떨어뜨린다는 문제가 있지만 팀정렬에서는 충분히 작은 n의 줄였기 때문에 문제가 되지 않습니다.

 

Tim sort 예시

C*n(logn-x)+a 를 최적화 시키기 위해서는 x값은 최대화, a값은 최소화 해야합니다.

예시를 통해 살펴봅시다.

해당 이미지는 naver D2 블로그를 참고하였습니다.

 

데이터 나누기

첫 번째 배열을 2^2개 덩어리로 자른다고 가정해봅시다.

맨 앞에 두 원소 (10, 13)이 증가하고 있으므로 해당 부분배열은 증가하는 방향으로 부분 배열을 만들어줍니다.

만약 뒤에 이어지는 (9, 15) 부분배열이 증가하고 있고 그대로 합쳐도 된다면 합치지만 앞 부분배열의 두 번째 값 13이 뒤 부분배열의 첫번째 값 10보다 크므로 아쉽게 바로 합칠 수는 없습니다. 따라서 삽입정렬을 통해 값을 대입해 부분배열의 크기를 키워줍니다.

다음으로는 (18, 21) 부분배열인데 그대로 합쳐도 문제가 없으므로 굳이 삽입정렬없이 바로 합쳐줍니다.

(13, 11)은 감소하고 있으므로 새로운 부분배열을 만들고 위와 같은 논리로 뒤 부분배열들을 합치게 됩니다.

이와 같이 부분배열의 첫 두 원소를 통해 증가부분배열, 감소부분배열을 정의하고 2^x개까지는 삽입정렬을 통해 진행하고, 그 뒤에는 바로 합쳐줌으로서 부분배열의 크기를 최대한 키웁니다.

이 때 이러한 부분배열들을 run이라고 하고, 2^x를 minrun 이라고 합니다.

만약 데이터가 이미 정렬되어 있다면 다음 과정을 통해 하나의 run만 생성되기 때문에 그 때의 시간복잡도는 O(n)입니다.

 

데이터 합치기

감소하는 run 들을 역전시켜서 증가하는 run 으로 바꿔줍니다.

이제 run 들을 다 만들었다면 이들을 합쳐봅시다.

기존의 병합정렬과 같은 방식으로 run 을 합치기에는 각 run 의 크기가 제각각이라는 문제점이 존재합니다.

이러한 문제를 해결하기 위해서 run 이 생성될 때마다 이를 스택에 담아줍니다. 그리고 한가지 규칙이 존재하는데 스택안에서 run들이 크기 순으로 정렬되도록 말이죠.

 

다음과 같이 크기가 큰 A가 들어온다면 B와 C를 더해서 규칙을 맞춰줍니다.

이를 통해 비슷한 크기의 run 끼리의 병합이 가능해졌습니다.

크기는 맞췄지만 병합정렬은 추가메모리를 사용한다는 단점이 있습니다.

추가메모리를 최소화 하며 두 run을 합치는 방법을 알아봅시다.

 

 

 

위 영상 역시 naver D2를 참고하였습니다.

위 그림에서 보는 것과 같이 우선 두 run 중 작은 것을 복사합니다. 두 개의 크기가 같다고 하면 최악으로 n/2 만큼의 메모리가 더 필요하겠죠.

그 뒤 원래 배열에 하나씩 비교해가며 값을 채워가는 과정을 반복합니다.

 

이를 더 최적화하기 위해서 병합이 필요없는 데이터를 미리 지정해놓을 수도 있습니다.