We’ll be implementing a version of the quicksort algorithm in Python. Quicksort is an efficient way of sorting a list of values by partitioning the list into smaller sub-lists based on comparisons with a single “pivot” element.
Our algorithm will be recursive, so we’ll have a base case and an inductive step that takes us closer to the base case. We’ll also sort our list in-place to keep it as efficient as possible.
Sorting in place means we’ll need to keep track of the sub-lists in our algorithm using pointers and swap values inside the list rather than create new lists.
We’ll use pointers a lot in this algorithm so it’s worth spending a little time practicing. Pointers are indices that keep track of a portion of a list. Here’s an example of using pointers to represent the entire list:
my_list = ['pizza', 'burrito', 'sandwich', 'salad', 'noodles'] start_of_list = 0 end_of_list = len(my_list) - 1 my_list[start_of_list : end_of_list + 1] # ['pizza', 'burrito', 'sandwich', 'salad', 'noodles']
Now, what if we wanted to keep
my_list the same, but make a sub-list of only the first half?
end_of_half_sub_list = len(my_list) // 2 # 2 my_list[start_of_list : end_of_half_sub_list + 1] # ['pizza', 'burrito', 'sandwich']
Finally, let’s make a sub-list that excludes the first and last elements…
start_of_sub_list = 1 end_of_sub_list = len(my_list) - 2 my_list[start_of_sub_list : end_of_sub_list + 1] # ['burrito', 'sandwich', 'salad']
Nice work! We’ll use two pointers,
end to keep track of sub-lists in our algorithm. Let’s get started!
In qs.py, define our
quicksort function with
end as parameters.
pass in the body of the function to start.
pass statement with a base case.
We’re going to be passing in the same list as an argument for each recursive call, but
end will mark what part of the list we’re considering.
Our base case is when the list from
end contains one or zero elements.
["race cars", "lasers", "airplanes"] start = 1 end = 1 # start == end # A sub-list starting at index 1 and concluding at index 1 # ["lasers"] start = 2 end = 1 # start > end # A sub-list start index 2 and concluding at index 1 # 
If the base case is met, then
return from the function.
Let’s start with a simple inductive step that takes us closer to the base case we’ve just defined.
if statement, print out the element at
start by one and recursively call
Test it out by calling
quicksort on the
colors list. You should see each color except the last printed out.