We're going to be looking at the very famous old\h algorithm called Quicksort. It's very clever and\h\h
it's very fast but it can also be very simple.\h So what I'm actually going to show you today is\h\h
how you can do Quicksort in just five lines\h of code. Where did the Quicksort algorithm\h\h
actually come from? This is Tony Hoare or\h Sir Tony Hoare to give him his proper name\h\h
and he was a computer scientist from Oxford and\h actually he was Oxford's head of computer science\h\h
for many, many years. And he published in 1962 a\h very famous paper with a lovely one-word title,\h\h
it's just called Quicksort. And you know you've\h done something quite fundamental and important\h\h
when you can have a paper with a one-word title.\h So this was published more than 60 years ago,\h\h
it's one of the older algorithms in computer\h science, but actually Tony invented this algorithm\h\h
a few years before that in 1959, but the actual\h paper which everyone cites was published in 1962.\h\h
What we're actually going to do is see how to do\h quicksort in two different ways. So first of all,\h\h
I'm going to explain on the lovely computer file\h paper how to do quicksort with a simple example.\h\h
And then we're going to move over to the laptop\h and see how to write it in actual code and in\h\h
five lines of code. And what we're going to do is\h put the numbers from one to nine into these boxes\h\h
in random order. So let's put the one here, two,\h three, four, five, six, seven, eight, and nine. So\h\h
we've got nine numbers here in jumbled up order,\h and we want to think how can we actually sort\h\h
these. So the way the quicksort algorithm works is\h you first of all pick what's called a pivot value.\h\h
And for symmetry reasons here, and we'll see why\h in a second, I'm just going to pick the middle\h\h
value in the list, the 5 here, so highlight\h that in red. So we've picked our pivot value,\h\h
and the next step in the algorithm now is that\h we're going to divide up the remaining numbers,\h\h
depending on whether they're less than or\h greater than the pivot value. So we're going\h\h
to send the numbers which are less than the 5\h down the left-hand side, so we'll end up with\h\h
4 of these. And we're going to send the numbers\h which are greater than 5 down the right-hand side,\h\h
and we'll also end up with 4 of these. And this\h is just a really simple process now. We just go\h\h
through the list apart from the pivot, and if it's\h less than five we write it here, greater than five\h\h
we write it here. So two is less than five, so\h that goes down here. Seven is greater than five,\h\h
so that goes here, and we keep going. And again,\h we have to be very careful not to mess it up.\h\h
We've got four numbers here, less than five, and\h we've also got four numbers greater than five.\h\h
The next step in the algorithm is we're going to\h sort in some way these two sub lists. So suppose\h\h
we sorted these numbers here. We're going to get\h four numbers. We're going to get one, two, three,\h\h
four. And suppose we sorted in some way, and again\h we'll come back to this in a second, we sort these\h\h
numbers here and we will get six, seven, eight,\h and nine. And then the final step in the algorithm\h\h
is the kind of obvious one. we've got two sorted\h sub-lists here. We've got 1, 2, 3, 4, 6, 7, 8,\h\h
9, and we've got our original pivot up the top\h here. All we're going to do is bring everything\h\h
back together. So we need nine boxes again. So\h we copy down the 1, 2, 3, 4. We copy down the\h\h
original pivot value, which we use to divide the\h list into two parts. And then we copy down the 6,\h\h
7, 8, and 9. So what we've done in moving from the\h top of the page down to the bottom of the page is\h\h
we've sorted the numbers from 1 to 9. But there's\h a couple of questions remaining, and actually I'm\h\h
going to put Sean on the spot now here. So first\h question for you, Sean. So how do we actually sort\h\h
the two sublists? Because I said we can sort them\h in some way. Any ideas how we could sort the two\h\h
sublists? Well, kind of presumably you've got to\h do the same thing again, right? You've got to pick\h\h
a pivot and do something like that. Yeah, exactly.\h So you do the same thing again. You just apply the\h\h
quick sort algorithm again. So we could take\h the numbers 2, 4, 1, 3, pick a pivot, divide\h\h
up the numbers, and do the sorting and merging.\h And it's a recursive algorithm. So quick sort is\h\h
defined in terms of itself. We divide up into two\h parts based on a pivot value. We recursively sort\h\h
the two parts using the same algorithm. And then\h we combine everything together at the end. But\h\h
when you're writing recursive programs, you always\h have to worry, how do they stop? So can I ask Sean\h\h
another question again. There needs to be an end\h case, is that right? Yeah, exactly. So you have to\h\h
stop. So when does this algorithm actually stop?\h So I'm just thinking about 2, 4, 1, 3. So if you\h\h
had, I don't know, pick 4, you've got 1, 2, 3.\h I don't know, how do you pass? So the algorithm\h\h
stops when you have no numbers left, because\h every time you call this algorithm recursively,\h\h
the sublists are going to be smaller, because you\h have a pivot value. So you might like have a pivot\h\h
of 1, right? As in you've only got one number,\h so you can't pivot. And then there'll be maybe\h\h
nothing left to actually sort. So the kind of\h base case for the algorithm or when the recursion\h\h
stops is when you don't have any numbers left. So\h that's the way QuickSort works in pictures. You\h\h
pick a pivot, divide up based on the two values,\h recursively sort and then merge back together at\h\h
the end, and the algorithm stops when you don't\h have any numbers left. What we're going to do now\h\h
is move over to the laptop and see how to do\h it in code. And as by the title of the video,\h\h
it's going to be five lines of code. So of course\h I'm going to use my favorite programming language\h\h
which is Haskell, which is a functional language,\h it's very concise, but everything I'm going to\h\h
show you today you can do in basically any high\h level language today that's got some kind of nice\h\h
facilities for manipulating lists. But Haskell is\h a good choice because it's so concise. So what I'm\h\h
going to do is start up an editor, I'll just make\h a temporary file here for putting the code in,\h\h
and we're going to write a quick sort function. So\h the quick sort function takes a list as an input,\h\h
and it gives a list as an output. And as we talked\h about a few minutes ago, the base case for the\h\h
definition is if you quicksort a list with nothing\h in it, then that stops the program running and\h\h
you get a list with nothing in it. So this is the\h base case for our definition. And the tiny piece\h\h
of notation here is in the language I'm using,\h the empty list is a square bracket followed by\h\h
a closed square bracket. But in other languages,\h it may be slightly different. So the other case,\h\h
which is the interesting case, is how do you\h quicksort a non-empty list? And this is the\h\h
only other tiny bit of notation, which I need\h to maybe explain here. This notation here means\h\h
a non-empty list where x is the first thing.\h That's actually going to be our pivot value.\h\h
We're going to have the first thing in the list\h being the pivot rather than the middle. And xs\h\h
is everything else in the list. So this is just a\h way of breaking down a list into the first thing,\h\h
which is going to be our pivot value and\h everything else in the list. And then we\h\h
can just go back to the example and think how do\h you actually quick sort a list? Well what we're\h\h
going to do is we're going to have the smaller\h numbers in a list so I'll call that smaller\h\h
and we're going to have the larger numbers in the\h list and we'll call that larger and the way we get\h\h
these is very simple. To get the smaller numbers\h all we're going to do is filter out the numbers\h\h
which are less than or equal to the first value in\h the list, which is here called x, and that's our\h\h
pivot value. That was 5 in our example. So we're\h going to filter out the values smaller than x\h\h
from the remaining numbers xs. Okay, so nice and\h easy. This is a primitive in the language that\h\h
I'm using. It filters things out of a list. Other\h languages, this may be called something different,\h\h
but other languages will have a similar\h kind of feature. To get the larger numbers,\h\h
we can do exactly the same thing. we can filter\h out the numbers which are bigger than x from the\h\h
list of remaining numbers. And now we have the\h kind of second level of the picture which we had.\h\h
We had the numbers 1 to 9 jumbled up. We picked\h a pivot. Now we're picking the first value. We\h\h
divide the list up into two parts, the smaller\h numbers and the larger numbers. And then we can\h\h
think, how do we continue from here? So let me\h write the rest of the code. It's really short,\h\h
all of this. So qsort larger. So this is the\h entire code now. So let me explain the kind\h\h
of bit up here where we kind of put everything\h together. All we're doing here is we're quick\h\h
sorting the smaller numbers. So that was down the\h left hand side of the example which we did. Then\h\h
we're quick sorting the larger numbers. So that\h was down the right hand side where we had the 6,\h\h
7, 8 and 9 jumbled up. And then all we do is kind\h of combine everything together and put the pivot\h\h
value, which here is x, in the middle. So plus\h plus is the operator in this particular language,\h\h
which joins two lists together. Here, we're just\h putting the pivot into a little list on its own,\h\h
and then we just smash everything together.\h And basically this is the quicksort algorithm.\h\h
And what's interesting here is that this is\h just five lines of code. We have a base case,\h\h
which says if you quicksort an empty list, you get\h an empty list. And then we have four lines which\h\h
are dealing with the recursion, which are telling\h us how to quicksort a non-empty list. And for me,\h\h
when you see kind of quicksort in pictures, it's\h kind of intuitively obvious how it's working,\h\h
but you might think, do I really understand\h what's going on? But when you look at the\h\h
code here, that's it. I mean, this is a complete\h implementation of quicksort in just five lines of\h\h
code. And it's kind of hard to think how you could\h express the essence of this quicksort algorithm\h\h
any more concisely than we've got here. There's\h really no redundant symbols here. If you've seen\h\h
quicksort in some other languages, it may be kind\h of quite a few more lines. It could be up to a\h\h
page of code in some other languages. But if you\h use a very high level language, like the one I'm\h\h
using here, you can really express the essence of\h the algorithm extremely concisely. Let's see how\h\h
it actually runs in practice. And let's see what\h kind of performance it's got. So what I've done is\h\h
I've prepared another file called qsort,\h and let me load that into the system. So\h\h
what I've got here is three bits of code now.\h I've got the quicksort algorithm in five lines,\h\h
which we've just developed. I've also got another\h sorting algorithm here called insertion sort. And\h\h
I'm not going to go into the details of how this\h works. But the important point here is quicksort\h\h
is a fast algorithm. Insertion sort is a slow\h algorithm. And we're going to see that in practice\h\h
when we do a little example. And of course,\h we're going to need some random lists to actually\h\h
sort. So I've written a little bit of code here\h that's going to randomize a list of numbers. And\h\h
it doesn't actually properly randomize. I'm just\h using what's called a riffle shuffle here. So if\h\h
you've ever played cards, you know, you can often\h shuffle cards by taking an entire deck, splitting\h\h
it in half, riffling it, which means kind of\h interleaving the odd and even cards. And if you do\h\h
that a bunch of times, that's a kind of reasonable\h approximation to randomizing things. So you can\h\h
see at the top here, if I'm randomizing a list of\h numbers, I'm just going to riffle shuffle it five\h\h
times. But the details of this are not important\h here. So let's make a list of random numbers. So\h\h
let's take randomize one up to 5,000. So we've got\h 5,000 random numbers. Let's have a look at that.\h\h
So, well, it's not very interesting. It's just\h 5,000 random numbers. But now what we can do is we\h\h
can quicksort it. And if we quicksort this list of\h 5,000 random numbers, almost as soon as I hit the\h\h
return key, we get the result. It's sorted it into\h the correct order. And this is not running on a\h\h
compiler here. This is an interpreted programming\h language, which I'm using. So if I actually\h\h
compile this, this would be about 10 times faster.\h But even just on an interpreter, this is a fast\h\h
algorithm. So let's contrast this by seeing how a\h not-so-good sorting algorithm works. So insertion\h\h
sort. Let's try insertion sorting the same list of\h 5,000 numbers. Well, it's not even done 1,000 yet.\h\h
Now it's up to 2000 and it's taking kind of five\h or six seconds to sort 5000 numbers. And actually,\h\h
this gets even worse if we consider a longer list.\h Let's try randomizing 10,000 numbers. If I quick\h\h
sort that, it takes a bit longer this time, maybe\h a second or two. But this time, if I run insertion\h\h
sort, it's not even got to 500, 1000. and this\h is a really slow algorithm. Not only is Quicksort\h\h
kind of a very clever algorithm, it's also a very\h efficient algorithm. And what I've been trying to\h\h
show you here in this short video is that if you\h look at Quicksort in the right way, using a very\h\h
high-level language, like the one we've been\h looking at here, then Quicksort can also be a\h\h
very simple algorithm, which you can write in\h just five lines of code. I'd like to show you\h\h
one extra thing, Sean, and I have to get a bit of\h Haskell magic in here, you know me. So we're going\h\h
to have a look again quickly at the quicksort\h algorithm, just five lines of code. Something\h\h
that's interesting about it is that it doesn't\h just sort numbers, it can sort other numbers.