Implementarea algoritmului quicksort
În acest exercițiu, vei implementa algoritmul quicksort pentru a sorta o listă de numere.
În primul pas, vei implementa funcția partition(), care returnează indexul pivotului după ce a procesat lista de numere, astfel încât toate elementele aflate la stânga pivotului să fie mai mici decât acesta, iar toate elementele aflate la dreapta să fie mai mari.
În al doilea pas, vei implementa funcția quicksort(), care va apela funcția partition().
Acest exercițiu face parte din cursul
Structuri de date și algoritmi în Python
Exercițiu interactiv practic
Încearcă acest exercițiu completând acest cod de exemplu.
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