Разница в создании списка Python

Question

Я пытаюсь создать рекурсивную функцию для сортировки списка от низкого до высокого.Следующий код не работает

less = []
greater = []
def quicksort(array):
    if len(array)<2:
        return array
    else:
        pivot = array[0]
        for i in array[1:]:
            if i <= pivot:
                less.append(i)
            else:
                greater.append(i)
        return quicksort(less)+[pivot]+quicksort(greater)
print(quicksort([1,3,2,7,8]))

, но я использую код книги, он работает.Вы бы посоветовали мне почему?

def quicksort(array):
    if len(array)<2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if  i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less)+[pivot]+quicksort(greater)
print(quicksort([1,3,2,7,8]))

Answer 1

Вы используете global less и greater list s, так что вы собираетесь в конечном итоге наращивать list s все больше и больше и больше, повторяя ваши входные данныемного раз (примерно пропорционально количеству рекурсивных вызовов quicksort).less и greater продолжают расти до тех пор, пока вы не достигнете предела глубины стека или не исчерпаете память, и Python не умрет, чтобы защитить вас от себя.

Хуже того, вы сохраняете состояние между вызовами, поэтому вторая и последующие вещивы quicksort заканчиваете тем, что включаете мусор из предыдущих операций сортировки, даже если они находятся на таких коротких входных данных, что вы можете «сортировать» их тривиально.Ваш код будет работать, если вы сделаете less / greater локальным, инициализируя их заново при каждом вызове:

def quicksort(array):
    if len(array)<2:
        return array
    else:
        pivot = array[0]
        less = []     # Local!
        greater = []  # Local!
        for i in array[1:]:
            if i <= pivot:
                less.append(i)
            else:
                greater.append(i)
        return quicksort(less)+[pivot]+quicksort(greater)