파이썬 array.sort(), TimSort 알고리즘

 

Tim Sort

@rylanbauermeister Merge Sort

@Timo Bingmann AI mini-batch처럼 쪼개고 쪼개서 정렬한다.

소개 (Insert + Merge)

 TimSort 는 파이썬, 자바, Swift, Rust stable에서 기본으로 탑재된 sort() 함수의 알고리즘이다.

최고 O(n) 시간 복잡도를 갖고, stable 하며, 다양한 데이터에 적합한 정렬 알고리즘이다.

(시간 복잡도 : 최상(n), 평균(nlogn), 최악(nlogn), 공간 복잡도 : n)

(이 글에서 구현된 timSort는 계산해보면 모든 케이스에서 nlogn이 나온다)

(정렬 알고리즘에서 안정성(stability)란 값이 원래 순서(order)를 갖고 정렬을 할 수 있냐, 없냐이다.)

@wikiwand

TimSort 는 두 가지 정렬 알고리즘을 섞은 것인데, 바로 Insertion과 Merge이다.

(Quick Sort는 unstable, Merge Sort와 Insertion Sort는 stable)

TimSort 는 mini-run이란 딥러닝의 mini-batch와 비슷하게, 작은 단위로 쪼개서 정렬한다.

(주로 2^5, 32~64로 설정하여 시작한다.)

 

 예를 들면, 길이가 140인 배열이 있다.

길이가 32인 4개의 배열과 길이가 12인 배열로 나뉜다. 그다음 이 모든 배열을 삽입 정렬을 실행한다.

하지만, 마지막에는 길이가 12인 배열에 20개의 element들을 추가해서, 정렬이 실행된다.

 

구현

1. Insertion Sort 구현

def insertSort(array, left, right):  # in-place | stable
    '''
    Best O(n) Time | O(1) Space
    Average O(n^2) Time | O(1) Space
    Worst (On^2) Time | O(1) Space
    '''
    for i in range(left + 1, right + 1):
        temp = array[i]
        j = i - 1
        while j >= left and array[j] > temp:
            array[j+1] = array[j]
            j -= 1
        array[j+1] = temp
    return array

2. Merge Sort 구현

merge_collapse, merge_low, merge_high, merge_... timSort는 merge sort가 엄청나게 변형된 버전인데,

간단하게만 구현했다. 자세한 내용은 참고 소스 확인

# 최적화된 Merge Sort
def fastmerge(array1, array2):
    merged_array = []
    while array1 or array2:
        if not array1:
            merged_array.append(array2.pop())
        elif (not array2) or array1[-1] > array2[-1]:
            merged_array.append(array1.pop())
        else:
            merged_array.append(array2.pop())
    merged_array.reverse()
    return merged_array

3. timSort 함수 구현

MIN_MERGE = 32

def timSort(arr):
    def calcMinRun(n):
        """Returns the minimum length of a run from 23 - 64 so that
        the len(array)/minrun is less than or equal to a power of 2.

        e.g. 1=>1, ..., 63=>63, 64=>32, 65=>33, ..., 127=>64, 128=>32, ...
        """
        r = 0
        while n >= MIN_MERGE:
            r |= n & 1
            n >>= 1
        return n + r
        
    n = len(arr)
    minRun = calcMinRun(n)
    
    # min run 만큼 건너뛰면서 삽입 정렬 실행
    for start in range(0, n, minRun):
        end = min(start + minRun - 1, n - 1)
        arr = insertSort(arr, start, end)
    currentSize = minRun

    # minRun이 배열 길이보다 작을 때까지만 minRun * 2 를 한다.
    while currentSize < n:
        for start in range(0, n, currentSize * 2):
            mid = min(n - 1, start + currentSize - 1)
            right = min(start + 2*currentSize - 1, n - 1)
            merged = fastmerge(array1=arr[start:mid + 1],
                               array2=arr[mid + 1:right + 1])
            arr[start:start + len(merged)] = merged

        currentSize *= 2

    return arr

※ gallop + 특수 변수는 제외해서, 완벽한 timSort라 할 순 없다.

BinSort + Gallop Merge를 보려면 아래 게시물 참고

모든 케이스에서 nLogn이 나온다. 흠

4. 얼마나 빠른가?

아래 글 맨 아래 부분을 참고

choiseokwon.tistory.com/220

파이썬 정렬 알고리즘 모음 + 속도 테스트

 

위 글 timSort 시간 복잡도 계산 결과

O(n)을 만들려면 merge gallop등이 필요해 보인다.

Running timSort(random array)...
Completed timSort(random array): O(nlog(n))
Running timSort(sorted array)...
Completed timSort(sorted array): O(nlog(n))
Running timSort(reversed array)...
Completed timSort(reversed array): O(nlog(n))
Running timSort(partial array)...
Completed timSort(partial array): O(nlog(n))
Running timSort(Ksorted array)...
Completed timSort(Ksorted array): O(nlog(n))

 

시간 복잡도 계산기 : choiseokwon.tistory.com/231

Smooth Sort : (choiseokwon.tistory.com/217)

Count Sort : (https://choiseokwon.tistory.com/206)

Intro Sort : (https://choiseokwon.tistory.com/209)

Python C 코드 : https://github.com/python/cpython/blob/master/Objects/listobject.c

자바 코드 : http://hg.openjdk.java.net/jdk7/jdk7/jdk/rev/bfd7abda8f79

Python timSort (galloping) : https://github.com/hu-ng/timsort/blob/master/timsort.py