Python: диапазон параметров функции

Question

Я изучаю QuickSort и практикуюсь с использованием Python для ее завершения. Но случилось то, чего я не ожидал. Кажется, моя функция быстрой сортировки сортируется только один раз. Почему?

array = [3, 1, 4, 5, 6, 7, 2, 0, 8, 9]


def quick_sort(array):
    if len(array) <= 1:
        # print(array)
        # print('')
        return
    else:
        # print(array)
        # print('')
        pivot = array[0]
        i = 1
        j = len(array) - 1
        while i != j:
            while array[j] >= pivot and i < j:
                j -= 1
            while array[i] <= pivot and i < j:
                i += 1
            if i < j:
                array[i], array[j] = array[j], array[i]
                # print(array)
                # print('')
        if array[0] > array[i]:
            array[0], array[i] = array[i], array[0]
        # print(array)
        # print('')
        array_left = array[0:i]
        array_right = array[i + 1:]
        quick_sort(array_left)
        quick_sort(array_right)


def test_quick_sort():

    # print(array)
    quick_sort(array)
    print(array)


test_quick_sort()

Выход составляет [2, 1, 0, 3, 6, 7, 5, 4, 8, 9]. Если вы отмените все #, вы увидите результат каждого шага, который абсолютно корректен.

Answer 1

В python, когда вы разрезаете список, создается новый список со значениями.

list1 = [1, 2, 3, 4, 5]
list2 = list1[:3] #[1, 2, 3]
list2[0] = 5 #[5, 2, 3]

print(list1, list2) #[1, 2, 3, 4, 5] [5, 2, 3]

Любые изменения, внесенные в нарезанный список, не отражаются в исходном.

В вашей функции quick_sort вы разрезали список на левые и правые части и вызывали на них quick_sort. Это не влияет на порядок исходного списка.

Чтобы решить эту проблему, измените свою функцию, чтобы вместо этого взять список вместе с начальным и конечным индексом места сортировки.

def quick_sort(array, start, end):
    if end - start <= 1:
        return
    else:
        pivot = array[start]
        i = start + 1
        j = end - 1
        while i != j:
            while array[j] >= pivot and i < j:
                j -= 1
            while array[i] <= pivot and i < j:
                i += 1
            if i < j:
                array[i], array[j] = array[j], array[i]
        if array[start] > array[i]:
            array[start], array[i] = array[i], array[start]
        quick_sort(array, start, i)
        quick_sort(array, i, end)