Ho dovuto implementare l'algoritmo QuickSort per un compito in una lingua a mia scelta e ho scelto Python.QuickSort sul posto in Python
Durante le lezioni, ci è stato detto che QuickSort è efficiente in memoria perché funziona sul posto; Ad esempio, non ha copie aggiuntive di parti dell'array di input per le ricorsioni.
Con questo in mente, ho cercato di implementare l'algoritmo QuickSort in Python, ma poco dopo ho capito che per scrivere un pezzo elegante di codice avrei dovuto passare parti della matrice alla funzione stessa mentre ricorsivo. Poichè Python crea nuove liste ogni volta che lo faccio, ho provato a usare Python3 (perché supporta la parola chiave nonlocal). Quello che segue è il mio codice commentato.
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)
Ora, non sono sicuro se ho fatto bene il lavoro o mi manca qualcosa. Ho scritto una versione più pitonica di QuickSort ma sicuramente non funziona sul posto perché continua a restituire parti della matrice di input e le concatena.
La mia domanda è, è questo il modo di farlo in Python? Ho cercato sia su Google che su SO ma non ho trovato una vera implementazione sul posto di QuickSort, quindi ho pensato che fosse meglio chiedere.
Hai provato di memoria profiler Python che vi dà la linea con l'analisi memoria di linea. – Hemanth
Invece di scrivere una funzione interna e usare 'nonlocale' perché non si definisce la funzione' quicksort' come 'def quicksort (array, start = 0, end = None): se end è None: end = len (array) - 1 ... '?Inoltre, è pratica comune implementare separatamente una funzione 'partition', quindi il codice quicksort diventa:' q = partition (array, start, end) quicksort (array, start, q-1) quicksort (array, q + 1 end) ' – Bakuriu
È possibile passare' array' in modo ricorsivo senza copiarlo; non puoi semplicemente tagliarlo. Inoltre, non è necessario 'nonlocale' perché stai modificando solo il contenuto dell'elenco associato a' arr', non quale lista è vincolata. –