Implementing the quicksort algorithm
In this exercise, you will implement the quicksort algorithm to sort a list of numbers.
In the first step, you will implement the partition() function, which returns the index of the pivot after having processed the list of numbers so that all the elements that are to the left of the pivot are less than the pivot and all the elements that are to the right of the pivot are greater than the pivot.
In the second step, you will implement the quicksort() function, which will call the partition() function.
Deze oefening maakt deel uit van de cursus
Data Structures and Algorithms 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