Video 4-2: Quicksort

0:01 In the next section we'll look at quick sort, the second big sorting algorithm that is efficient in practice and in theory. Uh unlike merge sort, um it first uh does the work and then recurses. And the key step that quick sort is based on is this partitioning step. Uh pictographically, you originally have a an unsorted input where the elements are arbitrary, and afterwards you have this pivot point, which means some specific position where the value is such that anything to the left is below that value, and anything to the right is above that value. So, in other words, this element here separates small from large, and we can recursively sort the left and right part. Uh before we get there, again, let's quickly look at how the partitioning is done. And here I'm directly showing the efficient version with two crossing pointers um that avoids um unnecessary swaps.

0:59 We pick our pivot element, more on how to do that in uh a little bit. Once we've chosen that, um we start from the left with one pointer or one iterator, and ask, is that element there? Is that larger or smaller than our pivot element? Here it's smaller, which means it's already on the on the correct side, on the left side.

1:24 For the next one, that's not the case. This is larger than the pivot, so it needs to somehow it end up in this right half of the of the input. For now, we don't move it, we just keep note of the fact that this is not in the place where it should be. Uh at this point, we start from the other end of the input and walk downwards. So, here we compare this element to the pivot element. It's larger, which is on the right end of the array, that is the right thing to have. Uh so, we can leave that where it is. But then, when we go to the next element, we find one that is small on this side. And now we found two elements, both of which are on the wrong side, so just swapping them both puts them in the right place. And that's why this algorithm has an edge over alternative implementations. It uses these swaps to get two player elements in the right place.

2:15 And after that, we continue until um the two pointers have crossed. So, here are a few more where we have already the element on the right side. Then again, something large that needs to move right. Start on the other end of the array. This is already big where it's supposed to be. This is not. And so, one last swap puts these two in place. And then um we notice that we're done when the two pointers have met on the same spot or crossed even. Uh to get to this picture up here, we need to put the pivot in between these two partitions with one extra swap, and then we're we're done. Uh that's one round of partitioning. And note here that um unlike merging, this doesn't need extra space. We can entirely modify the array in place just using swaps. We also visit every element exactly once. Maybe arguably the pivot we visit many times, but there you can you can say that is cached. I really just look at three elements at a time that I need uh in cache, and then I can move on the pivot and the two elements that I'm pointing to.

3:25 And so, every element needs to be loaded to the cache only once. Whereas for merge sort, remember this was twice as expensive. I need to say first copy everything to the buffer and then merge back or merge to the buffer and then copy back. That reads and writes every element twice.

3:43 As a side effect of rearranging the array, we can return this position where the two pointers have met, and that gives us uh the position or rank of the pivot that we can use for uh the recursive structure of the algorithm. Uh what I've described on the example is written down in pseudocode here. It's the same code, I hope, uh as you've seen in algorithms data structures if you've done that this summer. Um, the advice is really, if you ever have to don't try to reinvent the wheel. There's many little details that you that can go wrong in this code and have gone wrong in the history of quicksort. So, rather not make these mistakes again.

4:29 To turn that into a sorting algorithm, we um as I said, first partition. For that, we have to choose a pivot. This is one of the third tuning knobs where quicksort can be made better or worse. Uh after we've done that, we call this partitioning function from just uh the previous slide. And that means we now know where this pivot point is in the overall array. And we can recursively sort everything to the left and everything to the right of this position.

5:04 The choice of the pivot is important, and this is the classic example of where adding a judicious choice of randomness helps. We've discussed that yesterday with universal hashing. Here, it is much easier. All we need is to make sure that the pivot is not picked from some some fixed position because then some adversary input can with not too much difficulty make us uh always perform a a bad case. I'll I'll come to that in a second. Um the really practical choice should be just pick a random position or maybe pick three random positions and take the better the middle one. All of these are are much better options.

6:08 I was careful not to mention the result here even though I've I've alluded to the fact that there's a bad case. It is not a trick question. I just tried to throw in every thinkable answer that people may have in mind. Um if you're bored you can think of whether you know an algorithm with the running times for each of these beta classes.

7:12 This this one's interesting. Log log n of course, right? I mean you can you can always craft one. Famous or say uh has been used in exam questions at some point in the past. Here's a running time design some bonkers algorithm that takes that time. N log squared n is maybe among the more interesting. We'll we'll see an example next week. Either [snorts] way, um let me show some votes here. Unless someone is still busy uh voting.

7:52 N to the 5/3. Yeah, it's not even in my list unless you pick it like a pick the right epsilon. So the majority's of course correct. Um quick sort is horrible from the worst case perspective. It has quadratic time.

8:06 Uh basically what happens is if you pick a bad pivot, each time one of the recursive calls has n minus one elements. So, you go from n to n minus one to n minus two all the way down. And each time you spend linear cost for the partitioning. So, you just got the Gauss sum. And that's of course uh quadratic as as we've worked out in the past. So, that doesn't live up to the name of quicksort at all. Now, luckily this is not the typical case. Um to illustrate this let me uh show this now a bit more um interactively. It's cut off, but uh maybe you can see. So, let's do some some random thing. On the left here is um an input for quicksort, and we we apply quicksort. We always pick the first element as pivot. So, here the seven was used as pivot, then I get the left and right halves. Then I recurse on the on the left.

9:19 I pick the four, and I recurse on the left. I pick the two, right? So, you get uh the subproblems from quicksort. What is also shown here in these these lines is the child links of the recursive calls. So, there there was a uh a recursive call with two as the pivot. And it had two two child child recursive calls where the pivot was one and three respectively. That's what uh is shown here. And we do this until um every element has been pivot once. That's when we're done. Hold on.

9:57 That is one thing you could do. Now, let's take the same same numbers and insert them into an unbalanced binary search tree. I guess why not? That's what we do. Uh you start with the seven. Now, the four um is smaller than seven, so it goes left. The two is even smaller, so it moves all the way to the left there. The nine goes to the right, and so on and so forth. I guess you know how this looks. But, if you've carefully watched the animation on the left, you see um we can essentially trace what the elements do in the recursion tree of quicksort, and also the final tree. Uh if we do the last one, the final tree is exactly the same. And more than that, if you look at all the comparisons that were done in quicksort, this was done um in in the columns. I started with having the seven as pivot, then I compared all the other elements with with the seven.

11:00 That gave me one entry here in each of the columns. Then for the four, I still have many of the elements that are compared with the four because they're in this recursive subproblem, and so on and so forth. If I look in the tree what comparisons I do to insert the element, I have the very same comparisons, just a different order. To insert the four, I compare with the seven, and then with the four to kind of as a as a terminating condition. Uh that one maybe is a bit uh degenerate. Uh same for this seven compared with the seven. You could maybe uh leave off the diagonal. But, as you see from uh from the pictures, you do not just the same number of comparisons, you do the exact set of comparisons.

11:46 To the point that quicksort and an unbalanced binary search trees are really the same algorithm. It's just in different time order, and one is as a data structure where you do insertions one after the other, and the other is a a recursive algorithm.

12:15 Same animation is also in the in the lecture notes then. So this is um this very intimate relation between these two. Let me maybe uh say one caveat. Uh if you watch carefully what happened, um I did not use the partitioning method that I've shown you on the slides. Uh here you you need to use a stable partitioning method, which means all the elements here, the four, the two, the one, all the elements that go left appear in the same order that they had relative to each other in the original input. The statement is still true if you don't have that, but then there's a weird permutation applied in each step. It doesn't affect the expected cost or any of that, um but it makes the the picture a bit less less easy to follow. The important bit is that the number of comparisons, the expected number of comparisons in particular, uh remains the same even with the proper partitioning method. Question?

13:31 Uh both is true. You can say it's uh quick sort is the same as building the binary search tree by successive insertions. Uh or you can say suppose I already had that tree built, I can search each element once in the tree. It's the same thing here. Has the same comparison cost.

13:51 Uh so that's cute. Why did I show you that? Well, because we've analyzed binary binary search trees last week to death. Um we know that they can be degenerate as a linked list, then we have worst-case cost the same for quick sort. But this is very rare, and um I've shown you some uh tail inequalities just as a as a stated result. Um we can avoid that uh in the same with the same trick as in universal hashing. We can force our luck by deliberately putting in randomness. If we choose a random pivot in each step, that's the same as saying we pick the root of the binary search tree at each at each stage as um a random rank, and then we get the same cost as a random binary search tree. Yeah?

14:51 You said does it respect or Yeah, it returns the You can always do this. Um, let me maybe 5 million clicks later. Quickly show the code.

15:05 You can return this this position where you stop at the end. That's the J. Um, the way this this works, if you look at the invariant, is that these two pointers uh move towards each other, and then they meet at some position. And you can there's two cases whether they meet on the same spot or whether they cross over just a little bit. But you can work out that J is always the one where you should put the pivot. Uh, that needs careful inspection.

15:35 Um, if you want. There's an animation for everything. Uh, here's one that um shows the partitioning in action. You can put in different examples. It's precisely the code from the slides, and uh, what the first swap it did was picking a random pivot, even though here is a very bad choice. The first partitioning round was completely degenerate.

16:05 Uh, let's look at the next one. So, it picks a random pivot, and now it it compares. And you see once it's once the two uh pointers meet here I and J are on the same spot when it the loop terminates and so you can return that position. Okay, it moves one one further even. Um [snorts] after you swap the pivot there, J is the position where the pivot is. And there's there's the symmetric case um the the the other case where they meet on the same spot. That can also happen with duplicates for sure. I can work out that it's it works in both cases and you can always return this position.

16:55 The whole point of this connection was it's normally another half an hour to analyze quick sort, but like we've already done that work. Uh we can just appeal to the very same analysis. And um here there's two options. Again, you can either um either with this uh two options to use the analysis and then two options to randomize as on this slide. You can either say I'm going to hope that my input is random and then I'm doing an average case analysis. Uh then the same analogy still holds and the expected cost of quick sort are what they are. Uh or you can say I'm I'm not going to trust the universe to give me a a non-degenerate input. I rather enforce my luck using randomization and there you can either pick a random index in each position in each partitioning round as your pivot or you can just shuffle the entire input before you get started.

17:51 Uh it's a fun way to start sorting by first destroying any order. For quick sort, it's a good idea. Uh this this part I'll keep a bit quick. Um Uh the the precise analysis uses the cost measure we've used for merge sort, so we count element visits again. But that's precisely N in one partitioning round. Yep.

18:27 >> Uh yeah, we'll come to exploiting pre-sortedness. The thing with quicksort is it can't really exploit all kinds of pre-sortedness cleverly or like there's a a bit of an aster risk to this. Um it gets tricky to do all at the same time. The fastest implementations in practice don't really do that apart from exploiting duplicates maybe. But there that's um already jumping a bit ahead of this. Um we'll revisit that a bit in the tutorials. Uh so for the for the analysis here, if you assume we pick a random pivot or say say we shuffle the entire input at the start. Uh then that's the cost for sorting randomly permuted permuted elements.

19:15 And uh by using the same recurrence solving the same recurrence, we get our result from from last section or last unit. Uh it's the very same quantity this is very same recurrence, so I'm not going to go through it again. Uh what I want to point out here is that merge sort had two times n log n. Whereas quicksort has this this smaller constant factor in front 1 1.39. So it is indeed in this element visits cost measure is better than merge sort and this is also what you typically observe if you time it in a typical implementation. Uh same same comment as for uh the binary search trees, you can prove not just that this is the expected cost, but also almost always you're very close to that. Um let's not revisit that uh here again.

20:11 So as the as a general purpose method, quicksort tends to be the fastest. Uh in parentheses, if you have a an almost sorted input think again and we'll come back to that. Um but as worst case general purpose, if you wish, this usually is hard to beat. You have an average case that is n log n, and indeed with high probability you're very close to this good average case. You don't need extra space, and you still use memory essentially sequentially, so it also works well with caches. Um, the downside, apart from this astronomically unlikely worst case, which is really a no-brainer in practice if you randomize, you will not live to see this happen. Uh, the practical downside really is that it is hard to make stable and be in place and fast. And the fast implementation I've shown you is is not stable. It kills if you have equal elements that compare equal with respect to the sorting criterion, they may end up in a different order than they were in the original input.

21:14 It's easy to see that uh, I think there's also exercises on that. Uh, but it's rather easy to see if you start with the an input where everything is equal to the pivot and observe what the partitioning function does.

21:32 I think this one still stands that it is not known how to combine all these properties that we have a general generally fast algorithm, asymptotically fast and uh, in practice fast, but whatever that means, and stable, and in place, so using not much extra space. Combining all three seems generally tricky. Yep.

22:13 Yeah, basically. So, uh, to turn it around, stable means that elements that are equal >> They keep the same relative uh ordering. My usual example is suppose you have a table uh an Excel table with different columns and you want to sort the rows. And maybe you want names sorted in the usual way, first by first by by last name and among those with the same last name by first name. Of course, every uh spreadsheet calculation uh tool has has built-in a sort function that says exactly that, sort first by this column and then break ties using this column. If you didn't have this, you might do the following. You could sort first by the first name, the kind of uh secondary uh sorting criterion. And then after that, sort by last name. Of course, then um everything that is completely ordered by last name will be determined by the second sort. But if all the Simpson characters are sorted and they have Simpson as the last name, the first name determines the order in the input because the input for the second sort was sorted by first names.

23:49 And if the sort is stable, then the order by first name re- re- survives in the output. But if you used quicksort, then you might end up with completely jumbled Simpson characters. And who wants that?