Быстрая сортировка Python Рекурсия - как работает рекурсивная функция

Question

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

То, что я ищу, - это объяснение того, как функция _quicksort() работает, шаг за шагом. Любая помощь очень ценится!

def partition(xs, start, end):
    follower = leader = start
    while leader < end:
        if xs[leader] <= xs[end]:
            xs[follower], xs[leader] = xs[leader], xs[follower]
            follower += 1
        leader += 1
    xs[follower], xs[end] = xs[end], xs[follower]
    return follower

def _quicksort(xs, start, end):
    if start >= end:
        return
    p = partition(xs, start, end)
    _quicksort(xs, start, p-1)
    _quicksort(xs, p+1, end)

def quicksort(xs):
    _quicksort(xs, 0, len(xs)-1)

Answer 1

Это пример схемы разбиения Lomuto, в которой partition () разделяет входные данные на значения <= pivot, pivot, values> pivot. Результатом этого является то, что значения <= pivot будут поменяны местами так, чтобы они были меньше (начало последователя) от их конечной отсортированной позиции, значения> pivot будут поменяны местами так, чтобы они были меньше чем (конец последователя) от их конечная отсортированная позиция, и pivot (xs [end]) будет помещен в ее отсортированную позицию. Затем он рекурсивно вызывает себя для левой и правой групп. Каждый уровень рекурсии для группы помещает элементы в этой группе ближе к их окончательному отсортированному положению, и после достижения базового варианта (0 или 1 элементов) этот элемент находится в своем окончательном отсортированном положении.

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

Хотя быструю сортировку часто называют делением и Метод conquer, работа, выполняемая путем замены элементов ближе к их окончательному отсортированному положению, выполняется перед делением, и как только деление достигает базового случая 1 элемента, этот элемент теперь находится в своем окончательном отсортированном положении, и ничего не делается во время возврата обратно цепочка вызовов.

Взгляните на

https://en.wikipedia.org/wiki/Quicksort#Algorithm

https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme