파이썬 데코레이터 재귀 함수

Decorating recursive functions

 

사용할 데코레이터는 정렬 알고리즘이 정렬을 잘 했는지 체크한다.

def isSorted(func):
    def wrapper(array, *args):
        lib = bigO()

        result = func(array, *args)

        _sorted, index = lib.isAscendingSorted(result)
        if index == 1:
            msg = f"{result[index - 1]}, {result[index]}..."
        elif index == len(result) - 1:
            msg = f"...{result[index - 1]}, {result[index]}"
        elif isinstance(index, int):
            msg = f"...{result[index - 1]}, {result[index]}, {result[index + 1]}..."

        if not _sorted:
            # Just see the result if it doesn't sort correctly
            print(f"{func.__name__} doesn't sort correctly.\nAt {index} index: [{msg}]")
        else:
            print(f"{func.__name__} sorts correctly.")

    return wrapper

 

아래 거품 정렬같은 재귀 없는 함수에서는 잘 작동하지만

@isSorted
def bubbleSort(array):
    isSorted = False
    count = 0
    while not isSorted:
        isSorted = True
        for i in range(len(array) - 1 - count):
            if array[i] > array[i + 1]:
                array[i], array[i + 1] = array[i + 1], array[i]
                isSorted = False
        count += 1

    return array

# 출력: bubbleSort sorts correctly.

 

재귀 함수를 사용한 빠른 정렬에서는 함수를 부른만큼 데코레이터가 작동했다.

@isSorted
def quickSort(array, lo=0, hi=None):
    if hi is None:
        hi = len(array) - 1

    while hi > lo:
        p = partition(array, lo, hi)
        quickSort(array, lo, p)
        lo = p + 1
    return array
    
''' 결과
At 998 index: [...998, 990, 1000...]
quickSort doesn't sort correctly.
At 998 index: [...998, 990, 1000...]
quickSort sorts correctly.
quickSort sorts correctly.
quickSort sorts correctly.
quickSort sorts correctly.
quickSort sorts correctly.
'''

 

해결 방법

데코레이터를 제거하고, 데코레이터로 직접 함수를 불러야한다.

def quickSort(array, lo=0, hi=None):
    if hi is None:
        hi = len(array) - 1

    while hi > lo:
        p = partition(array, lo, hi)
        quickSort(array, lo, p)
        lo = p + 1
    return array


if __name__ == "__main__":
    isSorted(quickSort)(lib.genRandomArray(1000))