The Quicksort Algorithm
00:12 Quicksort is a sorting algorithm that uses a divide-and-conquer approach. It works like this: Given some data, you choose a pivot point, then create two lists, one with stuff less than the pivot point and the other with stuff greater than the pivot. Finally, you recursively call Quickstart on the sublists. Correct selection of the value for the pivot will make the algorithm much faster.
00:41 You’re trying to find the value that’s midway through the sorted list. You have to be careful with this, though. If you spend too much time figuring it out, you’ll never get a performant Quicksort, so it’s a bit of a balancing act to your guess.
01:09 Next is finding the pivot. The technique I’m using finds the median of the first, last, and middle item in the list. If you’ve got knowledge about your data, you might be able to make a better choice than this. Also, this will only work for numbers. If you’re sorting other kinds of data, you need a different way of picking the pivot.
Just going to scroll back up, and let’s take a look. The first call to the function takes the full list and the median of
3, so that’s the pivot. Now, time to calculate the sublists. Everything smaller than
3, the list with the pivots, and everything larger than
03:55 The sublists for the second level are then created, and once again, it’s time to recurse. This time, third level down, the list being sorted is empty. Then the second level’s larger list gets sorted, returning itself.
04:26 The version of Quicksort I showed you here is a bit more memory intensive. It needs copies of data for the sublists, along with the overhead of the lists themselves. There are versions of Quicksort that don’t require copies, but they’re harder to do in Python, and you typically see this in languages that support pointers.
The name of Quicksort is appropriate. It’s one of the faster sorting algorithms. If Python is your first programming language, you might not have come across Quicksort before, and that’s because Python has
.sort() built in. If you’re curious, the underlying algorithm for
.sort() in Python is not Quicksort, but something called Timsort. It is also pretty quick.
05:10 Its worst-case performance is faster than Quicksort, but there are other cases where Quicksort is faster, so it’s kind of a draw. Timsort does tend to work better if there are a lot of objects to dereference, and as everything in Python is an object, it kind of makes sense that Timsort was chosen as the defacto sorting in Python. That’s it for recursion.
Become a Member to join the conversation.