Implementera quicksort-algoritmen
I den här övningen ska du implementera quicksort-algoritmen för att sortera en lista med tal.
I det första steget implementerar du funktionen partition(), som returnerar pivotens index efter att ha bearbetat listan med tal så att alla element till vänster om pivoten är mindre än pivoten och alla element till höger om pivoten är större än pivoten.
I det andra steget implementerar du funktionen quicksort(), som anropar funktionen partition().
Den här övningen är en del av kursen
Datastrukturer och algoritmer i Python
Interaktiv övning med praktiskt arbete
Testa den här övningen genom att slutföra den här exempelkoden.
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