Algoritmo Quicksort con ricorsione: dubbio.

di il
1 risposte

Algoritmo Quicksort con ricorsione: dubbio.

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)

1 Risposte

  • Re: Algoritmo Quicksort con ricorsione: dubbio.

    Ciao, la risposta è in questo pezzo di codice:
    
    else:
               temp = alist[leftmark]
               alist[leftmark] = alist[rightmark]
               alist[rightmark] = temp
    
    in pratica scambia fra loro gli elementi che sono "mal posizionati" rispetto al pivot
Devi accedere o registrarti per scrivere nel forum
1 risposte