Het quicksort-algoritme implementeren
In deze oefening implementeer je het quicksort-algoritme om een lijst met getallen te sorteren.
In de eerste stap implementeer je de functie partition(), die de index van de pivot teruggeeft nadat de lijst zo is verwerkt dat alle elementen links van de pivot kleiner zijn dan de pivot en alle elementen rechts van de pivot groter zijn dan de pivot.
In de tweede stap implementeer je de functie quicksort(), die de functie partition() zal aanroepen.
Deze oefening maakt deel uit van de cursus
Datastructuren en algoritmen in Python
Praktische interactieve oefening
Probeer deze oefening eens door deze voorbeeldcode in te vullen.
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