**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 that you have an overview of how Quicksort works, let's try implementing it.

Quicksort works by picking a pivot value, then splitting the full list into two sub-lists. The first sub-list has all the values less than or equal to the pivot, and the second sub-list has all the values greater than the pivot. The quicksort function recursively calls itself to sort these sublists, and then to sort the sublists of those sub-lists, until the full list is sorted.

Now it's time to actually implement this in code.

```
import sys
from load import load_numbers
numbers = load_numbers(sys.argv[1])
# We already have the base case written. Any list passed in that consists of
# zero or one values will be returned as-is, because there's nothing to sort.
def quicksort(values):
if len(values) <= 1:
return values
# Now we need to create a list that will hold all the values less than the
# pivot. That list will be empty at first.
less_than_pivot = []
# We do the same for values greater than the pivot.
greater_than_pivot = []
# Next we need to choose the pivot value. For now, we just grab the first
# item from the list.
pivot = values[0]
# Then we loop through all the items in the list following the pivot.
for value in values[1:]:
# We check to see whether the current value is less than or equal to the
# pivot.
if value <= pivot:
# If it is, we copy it to the sub-list of values less than the pivot.
less_than_pivot.append(value)
# Otherwise, the current value must be greater than the pivot...
else:
# So we copy it to the other list.
greater_than_pivot.append(value)
# This last line is where the recursive magic happens. We call quicksort
# recursively on the sub-list that's less than the pivot. We do the same
# for the sub-list that's greater than the pivot. Those two calls will
# return sorted lists, so we combine the sorted values less than the pivot,
# the pivot itself, and the sorted values greater than the pivot. That
# gives us a complete, sorted list, which we return.
return quicksort(less_than_pivot) + [pivot] + quicksort(greater_than_pivot)
sorted_numbers = quicksort(numbers)
print(sorted_numbers)
```

Now, in your `numbers`

subdirectory, save the following to a file named `8.txt`

:

```
4
6
3
2
9
7
3
5
```

And run this command in your terminal:

```
python quicksort.py numbers/8.txt
```

It outputs our sorted list!

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

I don't know about you, but this whole thing still seems a little too magical to me. Let's add a couple print statements to the program so we can see what it's doing.

First, we'll add a print statement right before the first call to the `quicksort`

function, so we can see the unsorted list:

```
print(numbers)
```

We'll also add a print within the `quicksort`

function right before the recursive calls. Again, this string formatting code is just to keep the info aligned in columns.

```
print("%15s %1s %-15s" % (less_than_pivot, pivot, greater_than_pivot))
```

Let's try running this again:

```
python quicksort.py numbers/8.txt
[4, 6, 2, 3, 9, 7, 3, 5]
[2, 3, 3] 4 [6, 9, 7, 5]
[] 2 [3, 3]
[3] 3 []
[5] 6 [9, 7]
[7] 9 []
[2, 3, 3, 4, 5, 6, 7, 9]
```

- Each time
`quicksort`

goes to call itself recursively, it prints out the pivot, as well as the sublist of items less than or equal to the pivot (if any), and the sublist of items greater than the pivot (if any). - You can see that first it sorts the sublist of items less than the pivot at the top level:
`[2, 3, 3]`

.- It goes through a couple levels of recursion to do that.
- There are actually additional levels of recursion, but they're from calls to
`quicksort with a list of zero or one elements, and those calls return before the`

print` statement is reached.

- Then it starts sorting the second sub-list from the top level with items greater than the original pivot:
`[6, 9, 7, 5]`

.- You can see a couple levels of recursion for that sort as well.

- Finally, when both sub-lists are recursively sorted, the original call to the
`quicksort`

function returns, and we get the sorted list back.

What we've shown you here is just one way to implement Quicksort. Although the basic algorithm is always the same, the details can vary, like how you pick the pivot. Here are just a couple strategies:

- Randomly pick an item from the list passed to the
`quicksort`

function to use as the pivot. - Pick several items, average them, and use the item that's closest to the average as the pivot.

#### Troubleshooting

If you try running this on a file with thousands of repeated values, it's possible you'll get a `RuntimeError: maximum recursion depth exceeded`

error. This is because Python is set up to prevent functions from calling themselves recursively too many times. Although it's generally not a good idea to disable this behavior, it should be OK while you're just experimenting. You can allow additional recursive calls by adding this line after the `import`

statements in `quicksort.py`

:

```
sys.setrecursionlimit(10000)
```

Quick sort works by picking a pivot value, 0:00 then splitting the full list into two sub-lists. 0:02 The first sub-list has all the values less than or equal to the pivot and 0:05 the second sub-list has all the values greater than the pivot. 0:09 The quick sort function recursively calls itself to sort these sub-lists and 0:12 then to sort the sub-lists of those sub-lists until the full list is sorted. 0:16 Now it's time to actually implement this in code. 0:21 We already have the base case written, any list passed in that consists of zero or 0:25 one values will be returned as is because there's nothing to sort. 0:29 Now we need to create a list that will hold all the values less than the pivot, 0:34 that list will be empty at first, we do the same for 0:38 values greater than the pivot. 0:41 Next we need to choose the pivot value. 0:43 For now, we just grab the first item from the list, 0:45 then we loop through all the items in the list following the pivot. 0:48 We check to see whether the current value is less than or equal to the pivot, 0:53 if it is, we copy it to the sublist values less than the pivot. 0:57 Otherwise the current value must be greater than the pivot so 1:03 we copy it to the other list. 1:07 This last line is where the recursive magic happens, 1:13 we call quick sort recursively on the sub list that's less than the pivot. 1:17 We do the same for the sublist that's greater than the pivot. 1:21 Those two culls will return sorted lists, so we combine the sorted values list 1:24 in the pivot, the pivot itself, and the sorted values greater than the pivot, 1:29 that gives us a complete sorted list which we return. 1:34 This took a lot of prep work, are you ready? 1:38 Let's try running it, python, 1:40 quicksort.py numbers/8.text. 1:44 It outputs our sorted list, I don't know about you, 1:49 but this whole thing still seems a little too magical to me. 1:52 Let's add a couple print statements to the program so we can see what it's doing. 1:55 First, we'll add a print statement right before the first call to the quicksort 2:00 function, so we can see the unsorted list. 2:03 We'll also add a print right within the quick sort function, 2:06 right before the recursive calls. 2:09 Again, this string format encode is just to keep the info aligned in columns. 2:11 Let's try running this again and now you can see our new debug output. 2:25 Each time quick sort goes to call itself aposabli, it prints out the pivot as well 2:30 as the sub list of items less than or equal to the pivot, if any, and 2:35 the sub list of items greater than the pivot, if any. 2:38 You can see that first it sorts the sub list of items less than the pivot at 2:41 the top level, it goes through a couple levels of recursion to do that. 2:46 There are actually additional levels of recursion, but 2:52 they're from calls to quicksort with a list of zero or one elements, and 2:54 those calls return before the print statement is reached. 2:58 Then it starts sorting the second sublist from the top level with items greater than 3:01 the original pivot, you can see a couple levels of recursion for that sort as well. 3:06 Finally, when both sublets are recursively sorted, the original call to the quicksort 3:11 function returns, and we get the sorted list back. 3:16 So we know that it works, the next question is how well does it work? 3:19 Let's go back to our file of 10,000 numbers and see if it can sort those. 3:23 First though, I'm going to remove our two debug calls to print, so 3:28 it doesn't produce unreadable output. 3:31 A quick note, if you try running this on a file with a lot of repeated values, 3:34 it's possible you'll get a run time error of maximum recursion depth exceeded. 3:38 If you do, see the teacher's notes for a possible solution. 3:43 Now let's try running our quicksort program against the 10000 dot text file. 3:48 Python quicksort.py numbers/10000.txt. 3:52 There we go and it seems pretty fast, but how fast exactly? 3:59 Let's run it with the time command to see how long it takes. 4:04 Time python quicksort.py 4:06 numbers/10000.txt. 4:10 Remember we need to ignore the real result, and add the user and sys results, 4:15 it took less than a second of CPU time to sort 10,000 numbers with quick sort. 4:21 Remember that selection sort took about 13 seconds. 4:26 That's a pretty substantial improvement and with a million numbers, 4:30 selection sort took so long that it never even finished successfully. 4:33 Let's see if quicksort performs any better, 4:37 time python quicksort.pi numbers/1000000.txt. 4:42 Not only did quick sort sort a million numbers successfully, 4:55 it only took about 11 seconds of CPU time. 4:59 Quicksort is clearly much, much faster than selection sort, how much faster? 5:02 That's something we'll discuss in a later video. 5:07 What we've shown you here is just one way they implement quick sort. 5:10 Although the basic algorithm is always the same, the details can vary, 5:14 like how you pick the pivot. 5:17 See the teacher's notes for more details. 5:19

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

Sign up