파이썬의 정렬 알고리즘 Timsort (삽입정렬 + 병합정렬)

참고
1 d2.naver.com/helloworld/0315536
 2 파이썬 알고리즘 인터뷰
3 알고리즘 라이프
4 hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399
5 docs.python.org

파이썬의 정렬 메서드는 크게 두 가지다.
1) 리스트 객체에서만 쓸 수 있는 sort()
2) 모든 이터러블 객체에 쓸 수 있는 sorted()

sort()의 특징
1. 리스트에서만 쓸 수 있다.
2. 리스트는 mutable 한 객체이므로 sort() 메서드를 사용하면, 기존 리스트는 정렬된 리스트로 대체된다.

# 기본은 오름차순 정렬
data = [2, 3, 5, 54, 123, 2, 3, 1, 2, 4, 54]
data.sort()
data
[123, 54, 54, 5, 4, 3, 3, 2, 2, 2, 1]

# 내림차순도 가능 
data.sort(reverse=True)
data
[123, 54, 54, 5, 4, 3, 3, 2, 2, 2, 1]

sorted()의 특징
1. 이터러블 객체면 전부 사용가능하다. (리스트, 문자열, 딕셔너리, 집합...)
2. 새로운 리스트 객체를 리턴한다

# 기본 오름차순, 내림차순도 가능
data = [2, 3, 5, 54, 123, 2, 3, 1, 2, 4, 54]
data2 = sorted(data, reverse=True)
data2
[123, 54, 54, 5, 4, 3, 3, 2, 2, 2, 1]

#문자열
b = "sesefwef"
sorted(b)
['e', 'e', 'e', 'f', 'f', 's', 's', 'w']
"".join(sorted(b))
'eeeffssw'

#딕셔너리
d = {"banana" : 1, "apple" : 2, "grape" : 3}
d2 = sorted(d)
d2
['apple', 'banana', 'grape']

#집합
s = {2,3,4,5,1,0,9}
s2 = sorted(s)
s2
[0, 1, 2, 3, 4, 5, 9]

3. 정렬 옵션을 줄 수 있다

# 기본은 오름차순 (문자열의 첫번째 인덱스 순서대로 비교 정렬)
a = ['dba', 'abc', 'cab']
sorted(a)
['abc', 'cab', 'dba']

# 문자열의 마지막 인덱스를 기준으로 정렬
a = ['dba', 'abc', 'cab']
sorted(a, key = lambda s : (s[-1]))
['dba', 'cab', 'abc']

# 문자열의 두번째 인덱스를 기준으로 정렬
a = ['dba', 'abc', 'cab']
sorted(a, key = lambda s : (s[1]))
['cab', 'dba', 'abc']

# 문자열의 두번째 인덱스와 첫번째 인덱스를 기준으로 정렬
a = ['dba', 'abc', 'cab']
sorted(a, key = lambda s : (s[1], s[0]))
['cab', 'abc', 'dba']

# 문자열의 길이를 기준으로 정렬
b = ['123', '1234', '3', '4576', '3456764', '89645','38888']
sorted(b, key = len)
['3', '123', '1234', '4576', '89645', '38888', '3456764']

파이썬을 쓰는 코테에서 별다른 제약사항이 없다면,
대부분의 정렬문제 해결에는 sort(), sorted()가 가장 빠르다.
이유는 아래와 같다

파이썬의 sort(), sorted() 에 사용된 알고리즘
Timsort 알고리즘
1. 창안자인 Tim Peters의 이름을 따서 팀정렬(Tim sort)알고리즘이라 부른다 
2. 2001년 만들어진 알고리즘으로 파이썬을 위해 C 언어로 구현되었다.
3.  Python뿐만 아니라 Java SE 7, Android, Google chrome (V8), swift 등에서 표준 정렬 알고리즘으로 채택되었다. 

Timsort 알고리즘의 특징
1. '실제 데이터는 대부분 이미 정렬돼 있을 것이다' 라는 가정에 기반한 정렬 알고리즘.
2. 삽입정렬과 병합정렬을 적절히 조합한 알고리즘.
3. 현업에서 병합정렬, 퀵정렬 보다 더 널리 쓰이는 정렬알고리즘이다. 

Timsort 알고리즘의 아이디어

1. 현실세계의 데이터들은 완전 무작위로 배열돼 있기 보단
어느 정도 정렬된 상태로 배열돼 있는 경우가 많지 않을까? (예컨대 옷걸이에 대충 사이즈별로 걸린 옷들처럼)

2. 그렇다면 정렬을 해야하는 전체 배열을 작은 덩어리들로 잘라 
각각의 덩어리를 Insertion sort로 정렬한 뒤
merge sort로 병합하면 좀 더 빠르지 않을까?

이 아이디어가 왜 먹힐까?

아래 표를 보면 삽입정렬은 시간복잡도가 평균 n제곱으로 나쁜 편이고
메모리를 가장 덜 잡아먹으면서 준수한 속도를 내는 건 힙 정렬인 것을 알 수 있다.

왜 삽입정렬과 병합정렬을 조합해 만들었을까?

이하 이탤릭체는 모두 d2.naver.com/helloworld/0315536 에서 직접인용

"시간 복잡도가 선형로그시간 즉, O(n log n)라는 말은, 실제 동작 시간이 C x (n log n) + α라는 의미이다.
상대적으로 무시할 수 있는 부분인 α 부분을 제하면
(n log n)에는 앞에 C라는 상수가 곱해져 있어 이 값에 따라 실제 동작 시간에 큰 차이가 생기는데
이 C라는 값에 큰 영향을 끼치는 요소로
'알고리즘이 참조 지역성(Locality of reference) 원리를 얼마나 잘 만족하는가'가 있다."

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

Heap sort

"heap sort의 경우 대표적으로 참조 지역성이 좋지 않은 정렬이다.
왼쪽 이미지에서 확인할 수 있듯이
한 위치에 있는 요소를
해당 요소의 인덱스 두 배 또는 절반인 요소와 반복적으로 비교하기에
캐시 메모리에서는 예측하기가 매우 어렵다.
그렇기에 C는 상대적으로 병합정렬이나 퀵정렬보다 큰 값으로 정의된다."

"오른쪽의 quick sort의 경우
pivot 주변에서 데이터의 위치 이동이 빈번하게 발생하기에
참조 지역성이 좋으며 메모리를 추가로 사용하지 않는다.
실제로도 C의 값은 다른 두 정렬들보다 작은 값으로 정의되어 있고
평균 시간 복잡도는 셋 중에 가장 빠르다고 알려져 있다.
그러나 pivot을 선정하는 방법에 따라
최악의 경우 이차시간 즉 O(n**2)이 될 수 있다는 단점이 있다."
불안정 정렬이라는 점이 큰 마이너스로 작용한 것으로 보인다.

"왼쪽의 merge sort의 경우
인접한 덩어리를 병합하기에 참조 지역성의 원리를 어느 정도 잘 만족한다.
입력 배열 크기만큼의 메모리를 추가로 사용한다는 단점이 있지만
상수 C의 값이 너무 커지지 않게 동작하며,
추가 메모리도 많이 사용하지 않고,
최악의 경우에도 선형로그시간 O(n log n)으로 동작"하기 때문에
병합정렬이 팀소트에 조합된 것으로 보인다.

Insertion sort는 왼쪽과 같은 방법으로 동작한다.

"인접한 메모리와의 비교를 반복하기에
참조 지역성의 원리를 매우 잘 만족하고 있는 것을 확인할 수 있다
Insertion sort의 상수 C를 C1, 
정렬 알고리즘 중 C 값이 가장 작다고 알려져 있는 Quick sort의 상수 C 를
C2 라고 할 때,  n이 작다면
C1 x n**2 < C2 x (n log n) 이 성립한다고 한다. 
즉 , 작은 n에 대해선 삽입정렬이 퀵정렬보다 빠르다는 것이다."


정렬을 해야하는 전체 덩어리를 작은 덩어리로 잘라
각각의 덩어리를 Insertion sort로 정렬한 뒤
merge sort로 병합하면 좀 더 빠르지 않을까 하는 것이 Tim sort의 기본적인 아이디어라고 했다.
특히 전체 덩어리가 완전 무작위가 아니라 그 안에서 어느 정도 정렬이 된 상태라면
팀소트는 효과적인 정렬이 될 수 있겠다.

다음 링크의 영상을 보면 www.youtube.com/watch?v=NVIjHj-lrT4
삽입정렬된 덩어리들을 병합정렬하는 팀소트의 흐름을 볼 수 있다.



Timsort 알고리즘의 작동 원리

1. binary insertion sort

1. 먼저 덩어리 크기가 2의 5제곱(32) 또는 2의 6제곱(64) 개가 될 때까지 binary insertion sort를 진행한다.
(2의 거듭제곱 개로 맞추는 이유는 병합정렬이 최초에 2개씩 병합하기 때문이다)
(2의 5제곱에서 6제곱 개로 맞추는 이유는 적당히 작은 n개의 배열에 대해 삽입정렬을 실시하기 위해서다)
(여기서는 편의상 2의 제곱개인 4개가 될 때까지 진행한다)

2. binary insertion sort가 진행되는 방식은 다음과 같다. 
맨 앞의 두 원소만 놓고 보면 [10,13]으로 증가하고 있으므로
이 덩어리는 증가하는 원소가 담긴 덩어리로 간주한다.
즉 [10, 13] 부분은 이미 정렬된 하나의 부분이라 간주하고
삽입해야 할 위치를 이진탐색하여 찾는다. 

(그냥 삽입정렬을 한다면 이차시간 즉 O(n**2)이 걸린다.
인접항목을 비교하는 정렬방법은 모두 평균 이차시간이 걸린다 삽입, 선택, 버블정렬이 해당)

insertion sort

이진삽입정렬을 하면  참조 지역성은 떨어지지만 한 원소를 삽입할 때 O(n)번의 비교를 진행하는 대신
O(log n)번의 비교를 진행하게 되므로 작은 n에 대하여 좀 더 시간을 절약할 수 있다

정렬 결과 [9,10,13,15]이 된다. 
(이 덩어리를 minrun이라 부른다. 원래대로라면 2의 5제곱 (32) 또는 2의 6제곱 (64)개까지 정렬된 덩어리)
여기서 멈추지 않고 최대한 덩어리를 크게 만들기 위하여, 뒤의 원소들 또한 증가한다면 이 덩어리에 포함시킨다.
(여기선 운좋게 [18, 21]이 포함될 수 있다)
(이렇게 가능한 크게 만들어진 덩어리를 run이라 부른다)

3. 앞 부분의 binary insertion sort가 끝나면 뒷부분에서  binary insertion sort 가 진행된다.
뒤쪽 덩어리 맨 앞의 두 원소는 [13,8]로 감소하고 있으므로
이 덩어리는 감소하는 방향으로 정렬을 진행한다.
그 결과 [13,11,8,5]로 정렬되며 뒤의 [3]역시 운좋게 [5]보다 작으므로 같은 덩어리에 포함시킨다.

이렇게 increasing chunk, decreasing chunk로 구분하는 것은
생활에서 만나게 되는 데이터들이
증가하는 배열과 감소하는 배열이 혼합된 형태로 있을 거라는 가정에 근거한다.

즉 정렬하고자 하는 덩어리의 원소가 최대 64개 이하일 경우 팀소트는 우선 삽입정렬을 실시하는 것이다. 
위에서 언급했듯이 삽입 정렬은 작은 배열에서 매우 효과적인(빠른) 정렬방법이 될 수 있기 때문이다.

정렬하고자 하는 데이타가 이미 정렬된 경우, 최선의 경우엔 하나의 run만 생성될 수도 있으므로
(예를 들어 전체 배열이 운좋게 하나의 increasing chunk 일 경우)
Tim sort의 최선의 시간 복잡도는 O(n)이 될 수 있다. 

2. merge

위에서 삽입정렬한 각 덩어리 중 뒤쪽 덩어리는 내림차순으로 정렬이 되었었다.

뒤쪽 덩어리를 거꾸로 뒤집어 주면 두 덩어리 다 오름차순으로 바뀌게 된다.
이제 두 덩어리(두 run)을 정렬시킬 때
병합정렬을 사용하게 된다.

(병합정렬은 분할정복법을 쓰는 정렬방식으로
항목들의 집합을 더 작은 집합들로 쪼갠 후에 그 집합들을 정렬하는 방법이다.
집합을 반으로 나누는 것은 로그시간이고
그것들을 다시 합쳐 놓는 것은 모든 항목에 한번씩만 방문하므로 선형시간 작업이다.
따라서 병합정렬은 선형로그시간이 걸린다.
집합을 쪼개고(log n)나서 다시 합치는(n)데 걸리는 시간을 곱해 n log n을 얻는다)

merge sort

두 run 중 크기가 작은 run을 메모리에 따로 복사해 둔다.
앞쪽 run보다 뒤쪽 run의 크기가 작은 경우 
각 run의 끝 부분부터 크기 비교를 하여 큰 순서대로 뒤를 채우면서 진행한다.

위의 그림처럼 앞쪽 run이 뒤쪽 run보다 작은 경우엔
각 run의 시작 부분부터 크기 비교를 하여 작은 순서대로 앞을 채우면서 병합을 진행한다. 

이와 같이 두 run 중 크기가 작은 run을 메모리에 담으므로
병합을 진행할 때 최악의 경우 n/2의 추가 메모리를 사용하는 것을 알 수 있다.
일반적인 merge sort는 n만큼의 추가 메모리를 사용해야 하는데 반해 
팀소트의 병합정렬방식은 그 절반을 절약할 수 있는 것이다.

팀소트의 머지는 이 밖에도 run이 사전정렬 돼 있다는 사실을 이용해
더 적은 메모리를 사용하면서 더 빠르게 병합할 수 있는 몇가지 최적화 기법들(galloping 등)이 적용되어 진행된다.