Python знает, что список, который я использую для обеих функций в быстрой сортировке, одинаков? - PullRequest
Новая
       8

Python знает, что список, который я использую для обеих функций в быстрой сортировке, одинаков?

1 голос
/ 15 апреля 2020

Я использую алгоритм быстрой сортировки в Python, при котором он меняет значения на месте. Мой вопрос: как Python узнает, что я использую один и тот же список в функциях Partition и quicksort?

Как вы можете видеть ниже в моем коде для быстрой сортировки, замена позиции значений происходит только в функции разделения. Тем не менее, без необходимости возвращать список в функцию быстрой сортировки, он знает, что я поменял положение значений для списка в разделе, таким образом печатая отсортированный список. 

def quicksort(lst, start = 0, end = None): 
    if end is None:
        end = len(lst) - 1
    if start >= end:
        return
    p = partition(lst, start, end)
    quicksort(lst, start, p-1)
    quicksort(lst, p+1, end)

def partition(lst, start, end):
    pivot = lst[start]
    low = start + 1
    high =  end
    while low <= high:
        while lst[low] <= pivot:
            low +=  1
        while lst[high] >= pivot:
            high -= 1
        if low <= high: 
            lst[low], lst[high] = lst[high], lst[low]
            low += 1
            high -= 1

    lst[start], lst[high] = lst[high], lst[start]
    return high
numbers = [7, 6, 2, 4, 9, 1000]
quicksort(numbers)
print(numbers)

Пожалуйста, примите мой смиренные извинения, если я попросил что-то излишнее, так как я не смог ничего найти по этому поводу. В настоящее время я изучаю алгоритмы с помощью команды treehouse, но у них, похоже, ничего нет, кроме видео о быстрой сортировке, которое мало что объясняет. Если вы знаете где-то, где есть больше информации по этому вопросу, ваша помощь будет принята с благодарностью, если вы поделитесь ею со мной! Спасибо.

1 Ответ

1 голос
/ 15 апреля 2020

Это потому, что значения передаются по ссылке в python. Когда вы передаете lst в вашу функцию partition, вы фактически передаете ссылку на свой список в функции quicksort, а не копию списка.

...