Video 3-4: §3.2 Quicksort

0:00 Intro

0:03 All right. Uh in the next section, we'll look at quick sort, which is the second big efficient sorting algorithm that that's out there uh and it's very relevant in in practice.

0:14 Clicker Question

0:16 Again, to wake you up a little bit and see how many of you have done this before, let's try to get And maybe three on the live stream, who knows.

1:28 Okay, interesting. So, I'll I'll give you a minute. Let's Let's put it at least 60. That is 60. All right. So, we have a clear clear winner in terms of the majority, but lots of other answers as well. Uh um So, I would say the first first for me is the right one.

2:15 There was quite a few people for the for number D, I think, right? A few. Yep. So, um I think D the formulation is so vague that it's it's hard to say, "No, this is not what we're doing." Uh quick sort also swaps elements around, but the the key thing is is part one. Um so, around 2/3 or so.

2:40 Partitioning around a pivot

2:43 So, let me not rush rush through this too much cuz it's just too beautiful an algorithm and we will build on this a little later in this unit again. So, it's it's worth making sure this works. Yeah.

2:58 Uh okay, yeah. D D could be said is bubble sorting. Uh that's what I had in mind at least. But um admittedly, the description is so vague, right? You know, it swaps some out of order elements. Yeah, well, which which sorting algorithm doesn't? Uh yeah, good point. I'm I'm There's a lot of other sorting algorithms that we don't discuss. Mostly because uh a lot of you have will have heard about them and they're not that interesting. Like bubble sort is great, just no don't ever use it because there's hardly any scenario where it would be faster than pretty much anything else. So, I'll I'll just focus on the two that are relevant in practice.

3:41 For quick sort, we need this notion of partitioning. And I've uh I've drawn these kind of diagrams for merging before. So, here again, um I'm I'm representing the height is the value of of these elements and it's uh it's some uh continuous approximation. Just imagine this is a a large array with many many elements. The The idea of partitioning is we have something entirely unsorted. Could be just arbitrary uh arbitrary chaos. What we want is something like this. And now here the the point is that there is um a pivot point where I can draw a a vertical line. So, in value space, I can separate the elements to the right are all bigger than a certain line and the elements to the left are all below that certain line. That's the dashed red line. Uh and we usually think of this as happening at some position. Now, notice in this picture, this is not necessarily in the middle, right? Uh partitioning just says there should be some dividing line.

4:44 It could be higher or lower and where the split is between the smaller and the larger elements is also anywhere. We don't necessarily insist that it's exactly in the middle. Question?

4:59 No. Uh it doesn't have to be the median, that was the question. It's just So, partitioning in principle says there is some such point. Uh it could be it could be anywhere. Uh how does that look in in terms of an algorithm? So, this is just essentially a specification. That's what we would like to have at the end. How do we get there? Uh and I'll again, there's many ways to do this. I'll show you the the the one that's fast and relevant uh and um is a little more tricky to follow maybe. Bear with me for a minute. It works as follows. Uh we first select a pivot element. That will be this guy at the very end. But we for now just pick an arbitrary one and if the input is random, we might as well just pick the first one. At least that's what the example does. And now uh we start with um the next element after it and compare it with our pivot.

5:58 In this case, this is a smaller element. And uh remember at the end, the smaller elements should be on the left. So, this this is actually fine where it is. So, we just leave it alone and move on.

6:14 Then we go to the next one. This is obviously bigger, so it's it's not in the right place. So, we want to get it somewhere else. Now, this is where we can be smart or less smart. The less so smart methods try to get this thing get this thing moved away uh immediately. The smarter way is to delay that and say, "Okay, hold on. I'll keep a note that this this has to go, but let's start from the other end." So, you have uh a second pointer that scans from right to left and does the same game. So, this element is bigger than the pivot, but it's on the right side. So, this is this is fine. It can stay where it is. So, we leave it alone and go to the next one. Uh that's smaller. So, being on the right is the wrong thing for that one. But that's a match made in heaven, right? We now have a big one on the left and a small one on the right. So, let's just swap those two.

7:08 And then they're both happy and we can move on. That's that's how it works. Okay? Again, I I think many of you will have seen exactly this, but uh uh sometimes people do the slightly less sophisticated version. I wanted to show off the the fast one. So, we keep doing the same thing. If it's small and it's on the left, we can leave it alone. Same happens here. If we find a big one, we have to stop again and pass control to the pointer on the right. Uh that one's big, so on the right can stay where it is. Here we find another one. And so, again, two that are both in the wrong side, so we swap them. At this point, um we notice that we're done by the fact that the two pointers, they they started on the outside and then eventually they have to cross. And once that happens, that's our signal to stop.

8:03 And if I go a step back, so we have achieved basically this partitioning on this on this element on this array. The only thing that's left is that there's this pivot element that's currently still in the in the first position. But one more swap fixes that. Okay? And now we have our picture from above with the the dividing line. Okay?

8:33 Uh let's point out a few things. First of all, we didn't need any extra space. We needed to remember uh two or three pointers, but that's that's all. We didn't need this buffer area for merging. Uh if you carefully go through this again, you'll see that we visit each element only once. So, we move a pointer to to an element some at some point. We do a comparison with the pivot and then we either move it away right now or we wait. But every element is is just receiving a pointer once and maybe it's swapped. So, that's similar to merging. Uh and a nice outcome at the end, we're not just guaranteeing that the array afterwards has this shape. We can also easily return the position where the pivot landed so that we know what is the left and the right part. That's not so relevant for partitioning itself, but we'll use partitioning as a building block, right? And for that, it's useful to not have to find the position again.

9:33 So, we can just return this. Now, at this point uh uh sometimes the question pops up uh how often do you have to implement your own sorting algorithm? Not not ever usually because all programming languages come with a a sorting algorithm built in that is usually at least decent or heavily engineered and better what you could come up with on in a few hours. Uh so, you don't usually write your own sorting method. There's hopefully no normally no reason to. However, if it happens for some reason, maybe because he used partitioning uh directly in as part of some other thing. So, again, if you're programming in C++, it has a built-in partition function. I think Java and Python I'm not sure about Python. I think Java doesn't. So, maybe you have to write partition. If so, use this code. There's many subtleties to get wrong, which have to do with dealing with equal elements. So, there's a a historical story behind this.

9:38 Partitioning - Detailed code

10:40 Uh there was a famous bug report where someone the the standard Unix sorting implementation somehow became awfully slow. And what the person did was he had a file with just zeros and ones. And he wanted to count how many zeros are in that file. Now, okay, maybe it's bollocks to sort that file and find out how many zeros there are that way. On the other hand, you know, sorting is implemented, so why bother writing your own code if you can just call a function? So, he sorted that and found out that this goes super slow. And the reason was that the partitioning didn't deal with um equal elements really well. And the that's an interesting tricky story. I just wanted to share that the gist of it. So, this method will not completely explode in that instance. And it has other favorable properties. Other than that, I don't think we we need this code specifically, but I felt if I show you the fancy one and not the proper code, uh I wouldn't I wouldn't sleep well.

11:50 Yeah, I know. Okay, uh that was partitioning. We haven't sorted yet. Uh for for sorting to work, we get to again a recursive procedure.

12:01 And the outcome will be called quicksort because it happens to be fairly quick. Now, it was maybe a daft decision of Tony Hoare to call it quicksort right away. Uh but uh he he was right in the end. So, again, as for merge sort, if we just have a single element, nothing to do. Otherwise, uh we do well, a simple step to find some pivots. We'll we'll refine that step a little bit, but for now, you could just say um pick the first position as in the example. There's already some caveats. We'll come to it. Once you have a pivot chosen, you call this partition function. So, after that, your input is in this in this shape. I don't know. I Can I draw this nice enough?

12:55 So, yeah, if you're um dividing line, Now, I did draw it now where it looks like it's in the middle. I didn't want to. Uh but let's leave it. The thing is, if you have it partitioned, you can just recursively sort this part and this part independently. Everything that is on the left here is already smaller than everything on the right, so there's never ever needed some exchange from some element here to some element over there. They're already nicely separated. That's why after partitioning, we just have two recursive calls and we don't have to do anything when they come back. So, the split is whatever the partition function returns, which may or may not be in the middle, but we know it's it's this J. So, the part up to J is the recursive call, the part behind J is is the second part. And note that we exclude position J. This is exclusive notation.

13:56 Because the pivot is actually at its final position. After one partitioning round, we got one element where it will be at the end. It isn't moved anymore.

14:10 Uh okay, so coming back to the choice of the pivot, you could do just the first element uh or some other fixed position. That's a little dangerous for reasons we'll come to in a second. Um better choices are either do it randomly or at least um have several tries and uh pick the best out of a small sample. Um both are options that that are reasonable in practice. And why do we care about this so much? That's the point of this question.

15:20 I see a clear trend, but it's just um third of the people or so. So, I'll wait a little more. Okay, I guess many people have seen this before. So, maybe we speed up a bit. Uh it's too many answers. The big big bar comes here. And that's that's the right answer. Uh the interesting part will be why, so let's recap that a bit.

15:54 Quicksort & Binary Search Trees

15:58 And before we get there, I want to point out something that I don't know if you have seen this, but it's just uh a beautiful connection to something we have seen already. Uh for that, let's um let's have a look at at some example quicksort again. So, how does quicksort work? It picks a pivot and then it partitions all the smaller numbers, all the bigger numbers, and puts the pivot in in between. That was one partitioning step. Then, we recursively do the same in the left. So, again, pick a pivot, place it between the two partitions. Yep. What quicksort do you mean or what is Is there like Does the choice of pivot matter? You like picking the median as the pivot better or is it your choice? Uh so, the choice of the pivot definitely matters. Um well, we'll come back to the question what's a good what's a good way to do it.

16:49 Uh it's it's a little tricky in a way uh because you don't necessarily know up front what's a good one. But I think this this might lead us exactly to that to that uh question box. So, um We have partitioned the the left recursive call in the same way. In this example, I'm to make this correspondence really clean, I'm always picking the first element as the pivot. And I'm not using my fancy partitioning method, but I'm using a stable partitioning. As you see here, these these numbers that are smaller than four are smaller than seven, so in the first step, they appear in the same order down here. Uh that's important for the correspondence. It's not important for the real result. It's just to make it nicer to show. Uh I didn't want to comment on it, but now that uh you asked detailed questions, I think it's probably more confusing if not. Um Okay, let's let's speed that up a bit.

17:47 So, every part is eventually chosen as a every number is eventually chosen as a pivot, be it only because it's in this base case where we only have a single element left. Um right. And if I connect the recursive calls, so seven was the the topmost partitioning step and then we had two recursive calls, so I connect those and so on, we get a nice tree.

18:14 Now, let's do something else. Let's take these numbers and insert them in a binary search tree just in the order left to right as they come. So, we get the seven done. The four, smaller than seven, goes to the left, right? And you remember it replaces the leaf and we do this pointer and uh so on. Well, you've seen that last week. Uh two goes all the way to the left. Uh the nine is bigger than seven, becomes a right child, and so on and so forth, right? You can you can do this as some practice. Uh and if you do this, I guess obvious, the two are the same trees. It's the very same shape if you just look at this connection part here and the binary search tree we got by just inserting. That's interesting, right? If you think about it, it's no coincidence because what the binary search tree does is pretty much like partitioning.

19:05 And the correspondence goes bigger. So, I mean, everything that's smaller goes to the left, everything that's bigger that goes to the right. That's exactly what partitioning does and that's what binary search trees do. So, the the trees look the same. If you think about it, it's actually even the exact set of comparisons that are done either in quicksort or in building the trees the same. They do the same comparisons. They just reorder them. So, quicksort first compares everyone to the pivot and then goes on. In the binary search tree, we don't do that at the start, but every element that's inserted starts by comparing with the root, which is the first pivot. So, it's the same comparisons. And hence, if you count comparisons, the two things are the same. They have the same cost of sorting with quick sort or inserting into a binary search tree.

20:02 And I mean, apart from just showing this beautiful connection, you can obviously exploit this to analyze quick sort, right? We've already discussed what binary search trees are good for and where they are where they are bad. Um in particular, this this worst case for the height also turns out to be a worst case for quick sort. Because then you can you can work this out as a sum, the uh the case element has to travel down uh K minus one previous ones, so you get the sum of for the total cost. And that's quadratic, which uh most of you answered. So, you've seen some of this before. Maybe not via this connection to search trees, where this is becoming obvious in a way.

20:12 Quicksort-Worst Case

20:47 Um a good fix that I advertised for binary search trees already, but there I said, "Oh, this is a little tricky to do, so we'll skip it. I'll just teaser it." For quick sort, it's actually easy. If the input doesn't do you the favor of being in nice random order, you just make it so. And a not unreasonable way to sort is to first shuffle everything, destroy any existing order, and then run quick sort. That's by and large often the fastest way to sort. With a little asterisk that we'll come on come to on Wednesday, I guess.

21:27 Now, uh I said we can exploit this connection to analyze quick sort, and people have done this to much further extent. Um if we count the same way as for merge sort, the number of element visits that quick sort does, we can again get a recurrence. Uh it's a slightly less nice recurrence, so I'll spare you the details. Although I I really hope you have seen it in some undergraduate class or want to look it up. Um I can point you out to some places where it's written up. But I just want to present the result here. The final uh solution for this recurrence for quick sort is is the same. You have this N log base two of N, but with a different constant, and a much smaller constant than for merge sort. And so that's uh at a high level a good explanation why quick sort deserves its name. It's usually faster than merge sort.

21:32 Randomized Quicksort - Analysis

22:19 Uh so this is for the randomized version, and these are expected costs. So, it can happen that quick sort is awfully slow if you're extremely unlucky. Uh but if you properly randomize, you will not live long enough to see it happen. Because you can prove more, not just this expectation bound. Instead, you can prove something like the probability that you that that you see I don't know, five times the the expected cost uh goes to zero when N becomes bigger. If that statement doesn't uh feel very digestible, it's not too relevant. I'm just throwing this in to um to motivate the point that quick sort is not just good on in expectation. You can actually say more about it. Um yeah, maybe maybe maybe the intuition. For quick sort to be bad, the pivot has to be very bad, so either very small or very big, so that the split is not very even, very far away from the middle.

23:18 And to be really bad, you have to constantly be unlucky in this way. And that's unlikely. An individual bad pivot can happen, but you won't you won't get this all the time. That's unlikely.

23:29 Quicksort - Discussion

23:34 Okay, to finish off with quick sort, it is usually the fastest general purpose method for sorting. It deserves its name uh for many interesting reasons. So, most most practical implementations use some version of quick sort. Uh also because it's in place, so you can sort without big extra memory requirements. The average case is fast. That's what I what I just discussed. Uh same as for merge sort, the access is sequential. If you think back to partitioning, you always move these pointers towards each other, but they they always just jump one forward. It has this nasty worst case, but it's not really a problem if you randomize. The only real downside is that it's not stable. At least the fast version we've seen or partitioning without extra space. With a buffer, you can make it stable, but then you're back to merge sort territory. If you want to use the fast partitioning, it's not stable. Uh in a way, that's that's still an open question. Nobody has come up with a convincing answer for this. Can you find an algorithm that's simple, fast in practice, and stable, and in place?

24:43 Like if you drop any of these, I can show you how to do it. Um all together, it seems seems um annoying. And this is not so esoteric esoteric, right? You would like to have such a method.

25:02 Uh not quite. I mean, uh with a reasonable constant. I mean really fast in terms of you can implement it in in proper code, and it's faster than some textbook quick sort.

25:27 This Okay, we'll we'll touch on this a little bit later. Uh implementations in practice do more than just the basic versions. Um I don't know if uh combination of all these four print things.

25:55 Yeah, it's uh it's is a typical uh so, the question was um theta sounds like it should be average case, big O sounds like it should be worst case, and maybe omega then uh best case or or lower bound. I think this is often uh you often see people talking in these terms. So, it's it's very natural to come to that conclusion. But I think this is completely orthogonal. One is So, we're talking about on one side, asymptotic approximations for a mathematical function, which could be anything. It doesn't need to be a runtime. And on the other side, we're talking about the data model for an algorithm. Are we pessimistic, optimistic, or random? Uh that's one thing, and the two have don't have much to do with each other. So, say I can say I have a a big omega bound for the worst case, because I know it's at least that bad. Somehow, I have proven that, maybe.

26:50 Uh and similarly, the theta just means you have a lower and an upper bound that just have a constant factor in between them. And so you can say that about any function, and you can say that about the running time function for any of best, worst, average case, whatever you want to pick.

27:13 It depends what you can prove. Uh so, I I I prefer to use theta because it's the most precise uh of the three. Right? It tells you both it's not more than that and not less than that. It's exactly N log N with some well, some bounds, constant N log N, other constant N log N somewhere in between. If you can only prove an upper bound, then maybe you should just use O. Right? Yeah.

27:47 Combination of all these four print things. Yeah, it's uh it's is a typical uh so, the question was um theta sounds like it should be average case, big O sounds like it should be worst case, and maybe omega then uh best case or or lower bound. I think this is often uh you often see people talking in these terms. So, it's it's very natural to come to that conclusion. But I think this is completely orthogonal. One is So, we're talking about on one side, asymptotic approximations for a mathematical function, which could be anything. It doesn't need to be a runtime. And on the other side, we're talking about the data model for an algorithm. Are we pessimistic, optimistic, or random? Uh that's one thing, and the two have don't have much to do with each other. So, say I can say I have a a big omega bound for the worst case, because I know it's at least that bad.

29:05 Somehow, I have proven that, maybe. Uh and similarly, the theta just means you have a lower and an upper bound that just have a constant factor in between them. And so you can say that about any function, and you can say that about the running time function for any of best, worst, average case, whatever you want to pick.

29:32 It depends what you can prove. Uh so, I I I prefer to use theta because it's the most precise uh of the three. Right? It tells you both it's not more than that and not less than that. It's exactly N log N with some well, some bounds, constant N log N, other constant N log N somewhere in between. If you can only