Learn

Quicksort: Python

Quicksort Introduction

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]
# ['burrito', 'sandwich', 'salad']

Nice work! We’ll use two pointers, start and end to keep track of sub-lists in our algorithm. Let’s get started!

Instructions

In qs.py, define our quicksort function with list, start, and end as parameters.

Write pass in the body of the function to start.

Replace the pass statement with a base case.

We’re going to be passing in the same list as an argument for each recursive call, but start and end will mark what part of the list we’re considering.

Our base case is when the list from start to 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 which takes us closer to the base case we’ve just defined.

After the if statement, print out the element at start.

Then, increment start by one and recursively call quicksort with list, start, and end.

Test it out by calling quicksort on the colors list. You should see each color except the last printed out.

Sign up to start coding

Or sign up using:

Already have an account?