Quicksort

We'll have the complete code used in this video and the next in an upcoming instruction step!

You've seen "Bogosort", which doesn't make any progress toward sorting a list with each pass: either it's entirely sorted or it isn't. You've seen "selection sort", which moves one value over to a sorted list with each pass, so that it has fewer items to compare each time. Now let's look at an algorithm that speeds up the process further by further reducing the number of comparisons it makes: "Quicksort".

# Again, you can ignore these lines at the top. We're just using them to load
# a file full of numbers into a list.
import sys
from load import load_numbers

numbers = load_numbers(sys.argv[1])

# The Quicksort algorithm relies on recursion. To implement it, we'll write a
# recursive function. We'll accept the list of numbers to sort as a parameter.
def quicksort(values):
  # Quicksort is recursive because it keeps calling itself with smaller and
  # smaller subsets of the list you're trying to sort. We're going to need a
  # base case where the recursion stops, so it doesn't enter an infinite loop.
  # Lists that are empty don't need to be sorted. And lists with just one
  # element don't need to be sorted, either. In both cases, there's nothing
  # to flip around. So we'll make that our base case; if there are 0 or 1
  # elements in the list passed to the "quicksort" function, we'll return
  # the unaltered list to the caller.
  if len(values) <= 1:
    return values

# Lastly, we need to call our quicksort function with our list of numbers,
# and print the list it returns.
sorted_numbers = quicksort(numbers)
print(sorted_numbers)

• That takes care of our base case. Now, we need a recursive case.
• We're going to rely on a technique that's common in algorithm design, called "divide and conquer".
• Basically, we're going to take our problem and split it into smaller and smaller problems until they are easy to solve.
• In this case, that means taking our list and splitting it into smaller lists.

Suppose we load the numbers from our 8.txt file into a list. How do we divide it? It would probably be smart to have our quicksort function divide the list in a way that brings it closer to being sorted.

quicksort([4, 6, 3, 2, 9, 7, 3, 5])

Let's pick an item from the list. We'll just pick the first item for now, "4". We'll call this value we've picked the pivot, like the center of a see-saw on a playground.

We'll break the list into two sub-lists. The first sub-list will contain all the items in the original list that are smaller than the pivot. The second sub-list will contain all the items in the original list that are greater than the pivot.

Less than pivot          Pivot                Greater than pivot
[3, 2, 3]                 [4]                       [6, 9, 7, 5]

The sub-lists of values less than and greater than the pivot aren't sorted. But what if they were?

Less than pivot          Pivot                Greater than pivot
[2, 3, 3]                 [4]                       [5, 6, 7, 9]

You could just join the sub-lists and the pivot all together into one list, and the whole thing would be sorted!

[2, 3, 3, 4, 5, 6, 7, 9]

So how do we sort the sub-lists? We call our quicksort function recursively on them! This may seem like magic, but it's not; it's the "divide and conquer" algorithm design technique at work. If our quicksort function works on the big list, then it will work on the smaller lists, too.

Less than pivot          Pivot                Greater than pivot
quicksort([3, 2, 3])      [4]                       [6, 9, 7, 5]

For our first sub-list, we take the first item as the pivot again. That's 3. We break the sub-list into two sub-lists, one with everything less than the pivot, and one with everything greater than the pivot.

Less than pivot          Pivot                Greater than pivot
[2, 3]                    [3]                       []

Notice that there's a value equal to the pivot that gets put into the "less-than" sub-list. Our finished quicksort function is actually going to put everything that's less than or equal to the pivot in the first sub-list, but I don't want to say "less than or equal to" over and over, so I'm just referring to it as the "less than pivot" sub-list. Also notice that there are no values greater than the pivot. That's okay; when we join the sub-lists back together, that just means nothing will be in the returned list after the pivot.

We still have one sub-list that's more than one element long, so we call our quicksort function on that, too. You and I can see that it's already sorted, but the computer doesn't know that, so it will call it anyway just in case.

Less than pivot          Pivot                Greater than pivot
quicksort([2, 3])         [3]                       []

It picks the first element, 2, as a pivot. There are no elements less than the pivot, and only one element greater than the pivot.

Less than pivot          Pivot                Greater than pivot
[]                        [2]                       [3]

That's it for the recursive case; we've finally hit the base case for our quicksort function. It will be called on both the empty list of elements less than the pivot, and the one-item list of elements greater than the pivot... ...but both of those lists will be returned as they are, because there's nothing to sort.

Less than pivot          Pivot                Greater than pivot
quicksort([])                                   quicksort([3])

So now, at the level of the call stack above this, the returned sorted lists are used in place of the unsorted sub-list that's less than the pivot and the unsorted sub-list that's greater than the pivot.

These are joined together into one, sorted list. (Remember that any empty lists get discarded.)

[2, 3]

Then, at the level of the call stack above that, the returned sorted lists are used in place of the unsorted sub-lists there. (Again, they were already sorted, but the quicksort method was called on them anyway just in case.)

Less than pivot          Pivot                Greater than pivot
[2, 3]                    [3]                       []

The sub-lists are joined together into one, sorted list.

[2, 3, 3]

At the level of the call stack above that, the returned sorted list is used in place of the unsorted sub-list that's less than the pivot. So now, everything that's less than or equal to the pivot is sorted.

Less than pivot          Pivot                Greater than pivot
[2, 3, 3]                 [4]                       [6, 9, 7, 5]

Now, we call quicksort on the unsorted sub-list that's greater than the pivot. And the process repeats for that sublist.

Less than pivot          Pivot                Greater than pivot
[2, 3, 3]                 [4]             quicksort([6, 9, 7, 5])

We pick the first element, 6, as the pivot. We split the sub-list into sublists of elements that are less than and greater than this pivot. And we recursively call the quicksort function until those sublists are sorted.

Less than pivot          Pivot                Greater than pivot
[5]                       [6]                       [9, 7]

Eventually, a sorted sub-list is returned to our first quicksort function call.

Less than pivot          Pivot                Greater than pivot
[2, 3, 3]                 [4]                       [5, 6, 7, 9]

We combine the sub-list that's less than (or equal to) the pivot, the pivot itself, and the sub-list that's greater than the pivot into a single list. And because we recursively sorted the sub-lists, the whole list is sorted.

[2, 3, 3, 4, 5, 6, 7, 9]

So that's how the quicksort function is going to work. In the next video, we'll show you the actual code.