**Heads up!** To view this whole video, sign in with your Courses account or enroll in your free 7-day trial.
Sign In
Enroll

Start a free Courses trial

to watch this video

Now let's look at an algorithm that speeds up the process further by further reducing the number of comparisons it makes: "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.

You have seen bogo_sort. 0:00 Which doesn't make any progress toward sorting a list with each pass, 0:01 either it's entirely sorted or it isn't. 0:05 You've seen selection_sort, which moves one value over to an a sorted 0:07 list with each pass so that it has fewer items to compare each time. 0:11 Now let's look at an algorithm that speeds up the process further by further reducing 0:16 the number of comparison it makes. 0:20 It's called quicksort. 0:22 Here's some Python code where we'll implement quicksort. 0:24 Again, you can ignore these lines at the top. 0:27 We're just using them to load a file full of numbers into a list. 0:30 The quicksort algorithm relies on recursion. 0:34 To implement, it we'll write a recursive function. 0:37 We'll accept the list of numbers to sort as a parameter. 0:39 quicksort is recursive because it keeps calling itself with smaller and 0:43 smaller subsets of the list you're trying to sort. 0:47 We're going to need a base case where the recursion stops, so 0:50 it doesn't end in an infinite loop. 0:53 Lists that are empty don't need to be sorted, and 0:55 lists with just one element don't need to be sorted either. 0:58 In both cases, there's nothing to flip around. 1:01 So we'll make that our base case. 1:04 If there are 0 or 1 elements in the list past to the quicksort function, 1:06 we'll return the unaltered list to the caller. 1:10 Lastly, we need to call our quicksort function with our list of numbers and 1:13 print the list it returns. 1:19 That takes care of our base case, now we need a recursive case. 1:23 We're going to rely on a technique that's common 1:27 in algorithm design called divide and conquer. 1:30 Basically, we're going to take our problem and split it into smaller and 1:32 smaller problems until they're easy to solve. 1:36 In this case, that means taking our list and splitting it into smaller lists. 1:39 Viewers, a suggestion, the process I'm about to describe is complex. 1:44 There's just no way around it. 1:48 If you're having trouble following along, remember the video playback controls. 1:50 Feel free to slow the playback down, rewind or pause the video as needed. 1:54 After you watch this the first time, you may also find it helpful to rewind and 1:58 make your own diagram of the process as we go. 2:03 Okay, ready, here it goes. 2:05 Suppose we load the numbers from our 8.txt file into a list. 2:08 How do we divide it? 2:13 It would probably be smart to have our quicksort function 2:14 divide the list in a way that brings it closer to being sorted. 2:17 Let us pick an item from the list. 2:21 We'll just pick the first item for now, 4. 2:23 We'll call this value we've picked the pivot, 2:26 wike the center of a seesaw on a playground. 2:29 We'll break the list into two sublists. 2:31 The first sublist will contain all the items in the original list that 2:33 are smaller than the pivot. 2:36 The second sublist will contain all the items in the original list 2:38 that are greater than the pivot. 2:41 The sublist of values less than and greater than the pivot aren't sorted. 2:43 But what if they were? 2:48 You could just join the sublists and the pivot all together into one list, and 2:49 the whole thing would be sorted. 2:53 So how do we sort the sublist? 2:56 We call our quicksort function recursively on them. 2:57 This may seem like magic, but it's not. 3:00 It's the divide and conquer algorithm technique at work. 3:03 If our quicksort function works on the big list, 3:07 then it will work on the smaller list, too. 3:09 For our first sublist, we take the first item, it's the pivot again. 3:12 That's 3. 3:16 We break the sublist into two sublists. 3:18 One with everything less than the pivot. 3:20 And one with everything greater than the pivot. 3:22 Notice that there's a value equal to the pivot that gets put in to 3:25 the less than sublist. 3:28 Our finished quicksort function is actually going to put everything that's 3:30 less than or equal to the pivot in the first sublist. 3:33 But I don't wanna say less than or equal to over and over, so 3:36 I'm just referring to it as the less than pivot sublist. 3:40 Also, notice that there are no values greater than the pivot. 3:44 That’s okay. 3:47 When we join the sublists back together, 3:48 that just means nothing will be in the returned list after the pivot. 3:49 We still have one sublist that’s more than one element long. 3:53 So we call our quicksort function on that too. 3:56 You and I can see that it’s already sorted. 3:59 But the computer doesn’t know that, so it’ll call it anyway, just in case. 4:01 It picks the first element, 2, as a pivot. 4:06 There are no elements less than the pivot and 4:08 only one element greater than the pivot. 4:10 That's it for the recursive case. 4:13 We've finally hit the base case for our quicksort function. 4:15 It'll be called on both the empty list of elements less than the pivot and 4:18 the one item list of elements greater than the pivot. 4:21 But both of these lists will be returned as they are, 4:24 because there's nothing to sort. 4:27 So now, at the level of the call stack above this, 4:29 the return sorted lists are used in place of the unsorted sublist that's less 4:31 than the pivot and the unsorted sublist that's greater than the pivot. 4:36 These are joined together into one sorted list. 4:39 Remember that any empty lists get discarded. 4:42 Then at the level of the call stack above that, 4:46 the returned sorted lists are used in place of the unsorted sublists there. 4:48 Again, they were already sorted, but 4:52 the quicksort method was called on them anyway, just in case. 4:54 The sublists are joined together into one sorted list. 4:57 At the level of the call stack above that, the return sorted list 5:01 is used in place of the unsorted sublist that's less that the pivot. 5:04 So now everything that's less than or equal to the pivot is sorted. 5:07 Now we call quicksort on the unsorted sublist that's greater than the pivot and 5:11 the process repeats for that sublist. 5:16 We pick the first element, 6, as the pivot. 5:18 We split the sublist into sublists of elements that are less than and 5:21 greater than this pivot. 5:24 And we recursively call the quicksort function until those sublists are sorted. 5:25 Eventually, a sorted sublists is returned to our first quicksort function call. 5:31 We combine the sublist that's less-than-or-equal-to the pivot, 5:35 the pivot itself, and the sublist that's greater than the pivot into a single list. 5:39 And because we recursively sorted the sublist, the whole list is sorted. 5:43 So that's how the quicksort function is going to work. 5:48 In the next video, we'll show you the actual code. 5:51

You need to sign up for Treehouse in order to download course files.

Sign up