파이썬 list.sort() 정렬 알고리즘

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

알고리즘 스터디를 진행하면서 시간복잡도를 고려하는 중에 의문이 생겼다.

파이썬으로 코딩 테스트를 준비하면 보통 정렬을 할 때 파이썬에 내장되 있는 sort()를 사용하는데 이 때 어떤 정렬을 사용해서 정렬을 하는지 궁금증이 생긴 것 이다.

구글링 한 결과 TimSort 알고리즘을 사용한다는 것을 알게 되었다.

TimSort 알고리즘

Timsort

• Timsort is a hybrid sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsets of the data that are already ordered, and uses the subsets to sort the data more efficiently. This is done by merging an identified subset, called a run, with existing runs until certain criteria are fulfilled. Timsort has been Python’s standard sorting algorithm since version 2.3. It is now also used to sort arrays in Java SE 7, and on the Android platform

  Timsort는 여러 종류의 실제 데이터에서 잘 작동되도록 설계된 Merge 정렬과 Insert 정렬에서 파생된 하이브리드 정렬 알고리즘이다. 2002년 Tim Peters에 의해 Python 언어에 사용되기 위해 발명되었다. 이미 순서가 지정된 데이터의 부분 집합을 찾고 부분 집합을 사용하여 데이터를 보다 효율적으로 정렬하는 알고리즘이다. 이 작업은 특정 기준이 충족될 때까지 확인된 부분 집합인 런을 기존 런과 병합하여 수행한다. Timsort는 2.3 버전부터 Python의 표준 정렬 알고리즘이며 이제는 java SE 7 및 Android Platform 에서도 배열을 정렬하는데 사용된다.

• 파이썬, 자바, Swift, Rust stable에서 기본으로 탑재된 sort() 함수 알고리즘이다.
• 시간 복잡도: 최상(n), 평균(nlogn), 최악(nlogn), 공간 복잡도:n
• stable하다 (정렬 알고리즘에서 stability 란 원래 순서를 갖고 정렬을 할 수 있냐, 없냐의 차이)

Insertion Sort(삽입 정렬) 구현

# 시간 복잡도: 최상(n), 평균(n^2), 최악(n^2)
def insert_sort(array, left, right):
    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

Merge Sort(병합 정렬) 구현

def merge_sort(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

TimSort 구현

minrun : 임의의 run이 구성될 수 있는 최소 길이

Timsort는 run 생성시 run 크기를 동적으로 구한다. run을 만들 때 이미 정렬된 subsequence 기준으로 생성하며 만약 minrun보다 작게되면 insertion sort를 사용한다.

minimum run size(minrun)을 구하는 것은 data size에 의해 결정되며 elements가 64보다 작으면 minrun은 64가 되며 이처럼 사이즈가 작은 subsequence의 경우에 Timsort는 insertion sort를 수행한다. (이 처럼 작은 단위에서는 웬만해서는 binary insertion sort보다 빠른 정렬방법은 없기 때문에)

사이즈가 큰 array에서는 32~64 범위의 minrun을 가지고 array를 분할시킨다. 이러한 algorithm은 모든 array에 수행하며 크기가 64보다 작아질 때까지 한다.

MIN_MERGE = 64

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 = insert_sort(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 = merge_sort(array1=arr[start:mid + 1],
                               array2=arr[mid + 1:right + 1])
            arr[start:start + len(merged)] = merged

        currentSize *= 2

    return arr

참고자료

-https://shifu-oh.tistory.com/5

-https://choiseokwon.tistory.com/208

-https://en.wikipedia.org/wiki/Timsort

-https://orchistro.tistory.com/175

-http://svn.python.org/projects/python/trunk/Objects/listsort.txt