Мне пришлось реализовать алгоритм QuickSort для домашней работы на выбранном мной языке, и я выбрал Python.
Во время лекций нам сказали, что QuickSort эффективен с точки зрения памяти, потому что он работает на месте; то есть он не имеет дополнительных копий частей входного массива для рекурсий.
С учетом этого я попытался реализовать алгоритм QuickSort в Python, но вскоре понял, что для написания элегантной части кода мне пришлось бы передавать части массива самой функции во время рекурсии. Поскольку Python создает новые списки каждый раз, когда я это делаю, я пытался использовать Python3 (потому что он поддерживает нелокальное ключевое слово). Следующим является мой прокомментированный код.
def quicksort2(array):
# Create a local copy of array.
arr = array
def sort(start, end):
# Base case condition
if not start < end:
return
# Make it known to the inner function that we will work on arr
# from the outer definition
nonlocal arr
i = start + 1
j = start + 1
# Choosing the pivot as the first element of the working part
# part of arr
pivot = arr[start]
# Start partitioning
while j <= end:
if arr[j] < pivot:
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
i += 1
j += 1
temp = arr[start]
arr[start] = arr[i - 1]
arr[i - 1] = temp
# End partitioning
# Finally recurse on both partitions
sort(start + 0, i - 2)
sort(i, end)
sort(0, len(array) - 1)
Теперь я не уверен, хорошо ли я сделал эту работу, или я что-то упустил. Я написал более Pythonic версию QuickSort, но это, безусловно, не работает на месте, потому что он продолжает возвращать части входного массива и объединяет их.
Мой вопрос в том, как это сделать в Python? Я искал как Google, так и SO, но не нашел истинной реализации QuickSort на месте, поэтому я подумал, что лучше спросить.
