Video 3-3: §3.2 Quicksort

0:00 Intro

0:03 in the second part i want to talk about quicksort another efficient and well-known sorting method and let's see if you know quicksort already the attentive student might recognize the options

1:00 i'm tempted to show the results early because it seems quite clear shall we do the three two one let's put a bit of a competitive element in this uh yeah so the first answer is correct and vast majority got this

1:25 Clicker Question

1:42 so in this formulation split is what has split the elements around is a bit vague i guess the other term that people well historically at least use for this is partition uh partitioning can mean many things but okay it's stuck here um and what we what we mean by partitioning here is is again here's here's a picture you have an unsorted list that can have elements in an arbitrary order and it's partitioned if there is an element so that to a certain at a certain point this element is is located and then everything to the left of it is smaller than this guy and everything to the right of it is larger than this guy okay so in that picture uh this rectangle below that dashed line here has to be completely bright and the rectangle up here has to be completely empty that's another way to say it uh there are different ways how you can do this smarter ways and easier ways and better ways and faster ways i'll show you the kind of definitive way i think it's the way essentially how the original inventor uh described it tony hor and is still the one that's used in most libraries but it's not the one that is always taught because it's a little more

1:47 Partitioning around a pivot

3:04 finicky to program but here goes um you start by picking a pivot element that is the one that will eventually divide the two so this one this will be the one that you want to put in here and you can really pick any of them at the beginning doesn't matter um and then uh you want to start with two pointers that were that walk towards each other that's why it's also called crossing pointer technique one is on the left end and one is on the right end we'll come to that in a second and so uh you compare this element to the pivot and this is smaller and it's on the left so it's where it's supposed to be so we can just leave it alone

3:57 so we go to the next one this one's bigger so this is not good we have to do something about it it has to go to the right hand side now we could simply swap it with this one but that would have been a mistake because that's also big we don't know that yet but we see it as a human so instead the algorithm does a does something else it now takes this other pointer that starts from the right and passes the control to this one we compare this element with the pivot and now we find this is big so it should actually stay where it is and we leave it alone at some point we run into one that is smaller than the pivots and now we have a pair of elements identified where the two pointers are the one on the left is big and should go to the right the one on the right is small and should go to the left well that's a match made in heaven so we just swap those two okay

4:50 and then we continue again with our pointer on the left keep going so this is small can stay where it is this small can stay where it is this is big so it should go let me pass the control to the other side this is big so it can stay where it is this is small so it should go now we swap those two and then once those two pointers point to the same position that's our signal that we're actually done and that has happened now there's one one last step you want to do that is putting the pivot between those two segments then we've realized this picture up here as you may see everything here is filled everything up there is empty

5:34 this is entirely filled this is entirely empty a few things to note we didn't need extra space this was running in this original array that we were passed so this is running in place we visit each element exactly once with this pointer so sometimes we we keep it in cache for a while but we only need two elements that we're looking at plus the pivot so we don't really need to load and store the elements twice like in merge sort and that's one reason why quicksort is quick and deserves its name and the last thing just for for using this method in sorting then you have at the end of the partitioning you have a pointer to the position where the pivot is so you can return this one and this information will be used then

6:27 Partitioning - Detailed code

6:31 i spelled out some concrete code for the partitioning method because as i said earlier this one is very finicky to properly implement and get all the details correct it's no magic but there's many things you can do wrong that have uh unthought consequences where if you don't pay close attention it screws up some cases uh and i'm not saying this um uh well this is not an academic perspective all these mistakes have happened so people made these mistakes then people said oh my sorting method is very slow but i'm just sorting this harmless list and then people notice oh if you sort a list where all the elements are equal it goes quadratic not great things like that can be avoided so um just take this method if you ever need to but most of the time you will have an implementation in your library

7:26 the overall picture then for quick sort is is spelled out here again we have our recursion so it's again a divide and conquer algorithm but this time the work is done first and then the two recursive steps come at the as the last part unless we're already done we choose a pivot and we'll we'll talk about this in a second but it can be any element for now and then we call the partition function that i just showed you which returns the position where the pivot lands at the end and then we recursively sort sort everything to the left of the pivot and everything to the right of the pivot okay

8:08 now at this point there is a call to a method because choosing a good pivot for quicksort is again a little tricky you have to make compromises there if you just pick a fixed position like in the example i picked the first one that's actually a really bad idea you can think about why a much better idea is picking a random position where you actually throw a dice and then pick a random position and even if that is just a cheap approximately random position it's already good enough or you can do something slightly more advanced so you can take three elements and take the middle of the three what you want for your pivot is not to be very small or very big um

8:54 i think we'll come to that why that's the case i probably gave the answer to this one away if you were listening very carefully to what i said so same horrendous list of possible answers what's the worst case running time of quicksword

9:17 and yes i realize for some of you this will be like uh wake me up at 2am and i'll tell you was it last year that this was an exam question i put it one where am i telling this

9:48 it was on the easier side of the exam questions to be fair okay 46 can we get the 50 full but it seems quite clear three two one so yeah quicksort has this annoying feature that the worst cases is quadratic um which is so just to be clear about this is really really bad for sorting that's way too slow we don't want that

10:21 Quicksort & Binary Search Trees

10:24 but that's it is what it is uh i want to show you not a full analysis of quicksort but a nice connection that maybe you haven't seen and you might appreciate and it nicely connects to the previous unit so i really love this part

10:40 and then it allows me to comment on a few things but it's um it's also not very technical so that's that's nice suppose we're sorting with quicksort uh this list um and let's let's make some simplifying assumptions uh we're always picking the first element as pivot and the partition is not the one i've shown you but a simpler one that is stable you can basically ignore what i said it's just nicer to say to show it that way it works with the real partitioning one but it's more convoluted and i tried to push this under the rug but uh i feel the little devil on my shoulder says me i have to tell you so here's a way that quicksort could work it picks the first element as a pivot then it takes all the elements in the list that are smaller than this pivot and puts them to the left and it puts all the elements that are bigger to the right and as you can see it kept the relative order in this case which our partitioning method would not do but i said enough about this you can do it like this if you have extra space that was the first step though but we have to recurse right so we do this one

11:52 more time there's another split and we do this here another split and you keep going so and at the end like uh these are all empty recursive calls then uh if you connect the pivot elements how they relate in the recursive calls so there was the first the first step was using seven as a pivot and it had two child recursive calls for the left and the right part and i connected those to the pivots that were used in these recursive calls okay so clear what these with these lines are doing now let's do something that looks maybe unrelated first let's take this same list of numbers and insert it into a binary search tree we start with inserting the seven the tree is initially empty so nothing really happens the four is smaller than seven so it has to go to the left now the two is even smaller so it goes to the left of those two the nine is bigger than seven goes there the next one one has to bubble out down all the way down here so it goes there the three is smaller than this smaller than this but bigger than two so it should end up here and so on um and you may note that the trees are the same

13:14 okay we get the very same shape on the left and on the right uh and if you think about there's no magic going on this is just quicksort and binary search trees are very very related especially this variant of quicksort and yeah some some famous algorithms uh researcher john bentley said quicksort is like a like a binary search trees are like frozen quicksort or the other way around well it's a nice analogy that's in a way a binary search tree is a is a snapshot from sometime in quick sort

13:57 so if you take the recursion tree of quicksort you get the same as if you build a binary search tree by just insertions um and this now this this resemblance goes further if you look at what comparisons you've done to build the tree you do the exact same comparisons just in a different order so here in the binary search tree you compare everything to the root when you insert it and in quick sort you start with the first comparison for all elements in the first partitioning round by determining if it goes left or right but it's the same comparisons just reordered so that means whenever you analyze quicksort you might as well think about binary search trees or vice versa they're they're identical in their analysis

14:44 Quicksort - Worst Case

14:47 and that of course means uh all what i said about binary search trees last last time uh is also true for quicksort in particular if things come in this unfortunate order then we get the linear depth and for quick sort than the overall quadratic time

15:05 but also i said for binary search trees whenever there's some kind of randomness in the insertion order you don't get this bad behavior and the same is true for quicksort uh and here we are even more lucky than for binary search trees for binary search trees the best i could say was i won't usually happen don't worry too much but you can't guarantee it if someone deliberately says i'm inserting the elements in sorted order into your binary search tree then you have to do something about it and one solution was to use a balanced binary search tree in quick sort we have a different option no one forces us to do the stupid choice of pivots in from left to right because that's what would you would give you this one if you start with a sorted list already instead you can randomize the choice of the pivot and then you enforce the average case for binary search trees

16:08 a cute way to do this is a good quick sort implementation is first shuffling the input destroying any order that might have been there and then sorted again sounds a bit crazy but it's actually a quite reasonable way to do it

16:24 Randomized Quicksort - Analysis

16:27 you can say much more precisely what is happening in quicksort and in binary search trees same thing as i said for example you can count the number of element visits and the recursion is a little more tricky because we don't have the the same sizes even if you take powers of two as the input so we'll skip the analysis here but you can compute that it is 1.3 n 1.39 times n log n element visits on average and it's often close to that uh and you should compare this to the two and log n from merge sort so you see there's a there's a factor difference it's just a constant factor but it's quite significant if this is your running time and you can prove much more precise statements as i already hinted at in the binary search tree part

17:24 i think the intuition behind this is for quicksort to be really slow you have to not just one or through a few times catch a bad pivot which might happen you can't avoid that but you have to be constantly unlucky and that's just more and more unlikely the bigger the list gets

17:44 Quicksort - Discussion

17:47 so all that of that just for background um what can we say about quicksort in the standard scenario of sorting that we're looking at here it tends to be the fastest way to sort or at least a good variance based on it are the fastest the average case is still n log n even though the worst case is quadratic as noted here it's good that it works in place that was the big blemish of merge sort it needed this extra space and again the memory access remains sequential the partitioning again is is not jumping around in the array so it has the same virtue as merge sort on this side what we lose apart from the bad worst case is the stability if you do partitioning without extra space you lose stability it's pretty much uh one or the other you can't have both and have a simple algorithm so that's uh one open problem in algorithms is to find a simple algorithm that's fast in practice is stable and in place if you give up any of these four things there are solutions but not for all four and the first one is a little what is a simple algorithm is a bit hard to formalize

19:08 but it would be nice to have a solution to this or prove that it can't be done with some formalization of simple but yeah no one has come and come up with this yet