Ciao a tutti.
Sto studiando l'algoritmo QuickSort, e sto vedendo alcuni codici in Python 3, linguaggio che uso.
Questo codice ad es. funziona, ma anche se ho capito cosa fa la funzione partition, non capisco come la funzione QuickSort riesca a modificare la lista dato che la funzione partition restituisce un indice, non un elemento della lista.
Qualcuno puo' illuminarmi? Sono ore che cerco di afferrare il come fa, ma niente..
def partition(alist,first,last):
pivotvalue = alist[first]
leftmark = first+1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1
while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark -1
if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmark
def quickSort(alist,first,last):
if first<last:
splitpoint = partition(alist,first,last)
quickSort(alist,first,splitpoint-1)
quickSort(alist,splitpoint+1,last)
alist = [4,2,11,1,5]
quickSort(alist,0,len(alist)-1)
print(alist)