파이썬으로 분할 정복을 이용한 정렬 구현하기

코드 전문은 Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬 편에서 확인할 수 있다.

# 1. 퀵 정렬
def qsort(arr, left, right):
    pl = left
    pr = right
    pivot = arr[(left+right)//2]

    while pl <= pr:
        while arr[pl] < pivot: pl += 1
        while arr[pr] > pivot: pr -= 1
        if pl <= pr:
            arr[pl], arr[pr] = arr[pr], arr[pl]
            pl += 1
            pr -= 1

    if left < pr: qsort(arr, left, pr)
    if pl < right: qsort(arr, pl, right)

def quick_sort(arr):
    qsort(arr, 0, len(arr)-1)

# 2. 합병 정렬
def merge_sort(arr):
    def msort(arr, left, right):
        if left < right:
            mid = (left + right) // 2

            msort(arr, left, mid)
            msort(arr, mid+1, right)

            p = j = 0
            i = k = left

            while i <= mid:
                buff[p] = arr[i]
                p += 1
                i += 1

            while i <= right and j < p:
                if buff[j] <= arr[i]:
                    arrk] = buff[j]
                    j += 1
                else:
                    a[k] = a[i]
                    i += 1
                k += 1

            while j < p:
                arr[k] = buff[i]
                k += 1
                j += 1

    n = len(arr)
    buff = [None] * n
    msort(arr, 0, n-1)
    del buff

📝 메모

개인적으로 합병 정렬의 경우 여기서 구현한 코드가 더 이해하기 쉽다.