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.
This exercise is part of the course
Data Structures and Algorithms in Python
Hands-on interactive exercise
Have a go at this exercise by completing this sample code.
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