Implementazione dell'algoritmo quicksort
In questo esercizio implementerai l'algoritmo quicksort per ordinare una lista di numeri.
Nel primo passaggio, implementerai la funzione partition(), che restituisce l'indice del pivot dopo aver elaborato la lista di numeri in modo che tutti gli elementi a sinistra del pivot siano minori del pivot e tutti gli elementi a destra del pivot siano maggiori del pivot.
Nel secondo passaggio, implementerai la funzione quicksort(), che richiamerà la funzione partition().
Questo esercizio fa parte del corso
Strutture dati e algoritmi in Python
Esercizio pratico interattivo
Prova a risolvere questo esercizio completando il codice di esempio.
def partition(my_list, first_index, last_index):
pivot = my_list[first_index]
left_pointer = first_index + 1
right_pointer = last_index
while True:
# Iterate until the value pointed by left_pointer is greater than pivot or left_pointer is greater than last_index
while ____ < ____ and ____ < ____:
left_pointer += 1
while my_list[right_pointer] > pivot and right_pointer >= first_index:
right_pointer -= 1
if left_pointer >= right_pointer:
break
# Swap the values for the elements located at the left_pointer and right_pointer
my_list[left_pointer], my_list[right_pointer] = ____, ____
my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]
return right_pointer