Считается ли эта реализация быстрой сортировки «на месте»?

Question

Это реализация быстрой сортировки, которую мне легче понять, чем другие, которые я нашел. Хотя эта реализация не выглядит «на месте», как, по-видимому, должна быть быстрая сортировка. Я думаю, что это не «на месте», потому что вы возвращаете новый массив.

Правильно ли я считаю, что эта реализация «не на месте»?

def quick_sort(sequence):
    length = len(sequence)
    if length <= 1:
        return sequence
    else:
        pivot = sequence.pop()

    items_greater = []
    items_lower = []

    for item in sequence:
        if item > pivot:
            items_greater.append(item)
        else:
            items_lower.append(item)

    return quick_sort(items_lower) + [pivot] + quick_sort(items_greater)

Это еще одна реализация, которую я нашел, которая, как мне кажется, является версией быстрой сортировки «на месте». -> https://stackabuse.com/quicksort-in-python/

Если кто-нибудь может это подтвердить. Я был бы очень признателен. Спасибо!

Answer 1

Нет, это не реализация алгоритма быстрой сортировки «на месте».

Эту реализацию легче asp, но она очень неэффективна. Имейте в виду, что для массива, который вы пытаетесь отсортировать, он создает новый такого же размера, затем для его половины создается еще один, затем для половины или для него еще один и т. Д. .. Вы будете тратить много памяти на большие массивы.

Answer 2

Это определенно не на месте - вы создаете новые массивы (items_lower, et c)