Video 3-7: §3.7 Order statistics, quickselect, median of medians

0:00 Divide and conquer overview

0:03 in part three of the Sorting unit we'll look at a few other divide and conquer algorithms none of them is technically a sorting algorithm but because they have some similarity to how our key sorting algorithms work namely merge sword and quick sword they fit in this in this unit uh to round up a bit on what you can do with divide and conquer so let's see uh more concrete examples in a minute I want to briefly comment on on name uh comes from from a Latin phrase and uh is used in in slightly different meanings in different fields uh it has a maybe slightly negative touch if you use it in in the politics sense uh in particular you can kind of uh see disagreement uh we don't try to do that in algorithms but somehow the term got stuck some of the terminology in computer science science is just because people had this a strange sense of humor sometimes um and once the term is established it's a bit challenging to change it this one's not as bad I'll I'll have another example later in the course where I decided to rename things for us um in algorithms divide and conquer really just means this this rough uh vague principles uh of breaking a larger problem that we're trying to

1:30 solve into smaller independent sub problems so I think the important bit here many algorithms somehow break a problem into smaller parts for divide and conquer what we stress is that these are independent problems that you can solve independently um and we also usually assume that they kind of cover the entire problem uh for the experts this is to distinguish it from dynamic programming we don't really have to do that here so you somehow identify sub problems you serve solve them recursively so usually divide and conquer algorithms can nicely be described as recursive functions but you don't have to and then there's some step of uh putting things together we've seen various examples um uh we didn't talk about this in in detail um uh we can I can tell you offline if you're interested for merge sword um the breaking into steps uh into Parts was very easy we just split in the middle uh in parenthesis unlik unless we want to do Peak sword but let's ignore that so we just split it in two so the breaking up was very easy and then uh when we come back from the recursion the merging was the part where we spent most of the time uh and quick swort is a bit the opposite way around we spend a lot

2:56 of time of dividing with Partition we do the the main effort up front um and then we obtain the the sub problems as part of the as the output of the partition and binary search you could say is also a kind of divide and conqueror uh but you only appro you only follow through with one of the sub problems if you want you can put it in the same

3:31 Selection by rank problem

3:31 framew right so apart from the names let's see some concrete examples to make this a bit more concrete and um one is this idea of order statistics or also known as selection or selection by rank to motivate this a bit um a standard standard thing you want to do if you have numeric data and it's a bit too big to just look at it um I'm thinking here of of one-dimensional data so it's an an array of numbers of one one big Vector there's a few standard things that for example tools like pandas this python framework that maybe some of you have used for for data science tasks it has a standard method describe that gives you pretty much some of these functions and it's a standard practice to if you have a large data set of numbers to just look at these summary statistics first so I'm sure you know what mean and standard deviation R and Min and Max um slightly more esoteric but often very very useful are these order statistics for example the median and the median is just an element so that half of the elements are smaller and half of the elements are bigger with breaking ties in a reasonable way so uh um you have to make that a bit more

4:53 precise and we'll we'll actually do that in a in a way uh when we Define our algorithmic problem apart from the median you can can ask for other quantiles for example quartiles a quartile the lower quartile would be a value so that a quarter of the elements are smaller and three quarters or bigger then there's two other quartiles the second quartile is the median and the third is three quarters are below and you can generalize this of course now if you look at this from an algorithmic perspective all of these are easy to um easy to compute in in linear time where hisrs at least assuming that the range is uh that the number of bins is is small uh for the order statistics it's not obvious how to compute them in in linear time and so that's that's what this uh what this problem is

5:53 about so more formally um we call this the selection by rank problem and the input are two things it's an array of numbers or actually General objects uh another thing I I didn't mention here too much but you can only Define a mean on numbers where you can do arithmetic where you can add up numbers uh you can Define these order statistics for arbitrary objects that you can put into a relative order so these are more General you can ask for um the median of all last names in alphabetic order and you can check what comes first in that name it doesn't make sense to ask for the mean value of your last names I mean you can maybe Define some something but it's it doesn't make so much sense so these are um a bit more General as well okay um coming back to the the problem definition we have a an array of numbers let's keep it simple for for this one and we have a number that's the position that we'd like to have um and the way I form this is suppose you would sort the entire array and then look at position k at index K so we'll um we'll use this with the same same kind of convention we had

7:14 before it's all zero based then the answer um of this of this problem is what would you find at index K if you sorted the entire array so if you put uh n half in rounded appropriately you get the median you get the quartiles um and you can find minimum and maximum or the L largest uh by putting K to to the appropriate

7:56 value now an obvious obvious conclusion to solve this problem is you just sort the array and then pick pick out their number so uh I didn't even put this on this slide

8:18 time uh then we already know how to do this just sort the entire array uh the whole point of studying this problem in isolation is that you don't actually need to sort the entire array all you want is that one element at its specific position and it turns out we can find that much cheaper if you've seen this before the algorithm is called quick select uh maybe you know this but let me introduce It Anyways um from from scratch

8:36 Quick select algorithm

8:47 so the way to motivate this if you haven't seen it before I would say is is like this if you're given um a rank it's not easy to find the element that has that rank but if you're given uh an element Computing its rank is easy you just count how many elements are smaller and so in a way quick select uses one to do the other and shows that they're in some sense uh not as not as different as they first looked like so what do we do we pick an arbitrary element and find its rank how do we find the rank well we count how many are smaller uh if we by accident happen to pick the right element that one that we looked that we were looking for then we could stop and otherwise we have learned something namely if the rank of this element that we picked is too small then we know all elements that are even smaller than that element will also definitely be too small have too smaller rank so we can exclude all of those and that actually in includes that element that we picked itself and because it's zero based that's j+ one elements that we can exclude and the symetric case if the rank of the element that we picked is

10:09 too big we can also exclude uh a lot of elements hopefully and maybe no uh no surprise at this point um if you want to find how many elements are smaller and also exclude them afterward well you really want a partition so we can use exactly the partition function from quicksort to do both of these things in one go we find the rank of the element by the return value namely the position where the pivot went and that procedure already nicely separates the smaller and larger elements so we can use the very same kind of uh subroutines which is why I I did not spell this out if you scroll back 200 slides with all the animations which I I don't want to do now you find the codee for partition right we covered that in the quick sort section and we also have this method to choose the pivot that's in a way the same kind of story as for timsort uh for for for quick sword I'm getting mixed up it's the same story as for quicksort you don't want to pick a a fixed element necessarily because then you might be vulnerable to a worst case you could pick a random one that's not a bad choice and you could do um

11:30 compromises on this in practice let's suppose it's some arbitrary function we get the pivot we partition we get the rank of the element of the pivot that we picked if we were lucky we can just return that and stop and otherwise we have only one side of the recursion to still pursue so again if the rank of the pivot was too small we can ignore all the elements that are even smaller so we'll focus on the right half of the array or the right part it's not necessarily half right and otherwise we focus on the left part uh one small one small point if you have to do it if you have to recurse on the right side you have to adjust the rank that you're looking for because you're excluding elements and so um in in the way I formulated the problem here you have to adjust your your

12:29 rank uh how good is this so maybe not completely obvious but if you think for for 10 minutes about it you see the same worst case as for quick sort can happen uh suppose you're trying to find the minimum in the array so your K is zero but because the universe conspires against you you always you always pick as pivot the largest element in the array so in each round you exclude just that single element but you pay a linear your cost and so it gives you the same worst case as for quick sort uh on the other hand the expected cost is actually linear it's not n log n it's way better and the reason is we don't do the second recursive call we always just do one and so uh you have to be constantly unlucky with your pivot choice to see a high cost uh it doesn't need extra space it actually doesn't even need recursion if you look at the code here we only do one recursive step so by rewriting the code making the code a little more messy you can make this one big loop you don't need any recursion and so you can do without any extra space uh you can also tweak the same code to find say five different order

13:45 statistics in one go instead of just one um which is a bit more expensive than finding a single one but it's cheaper than calling quick sword quick select five times but that part part is not so not so vital so for for practical purposes quick select is fine and uh the programming librar is that provide a method for rank selection by rank like the C++ Library the the standard template library has a method uh function n element that is based on quick select uh we'll meet those two characters in the next unit a bit more so I tried to make this a bit of a dialogue between the practitioner programmer who's happy if it works most of the time and in most applications and the kind of theoretician that says uh I also want to have these um um provable guarantees the Eternal

14:01 Worst-case performance issues

14:44 truths of algorithms so he's not quite happy yet because um it's such a fundamental problem can we actually do this in guaranteed linear time worst case linear time and

15:03 it turns out the answer is yes this is one of those problems where um a lot of really smart people at touring Award winners you know touring awards are our Nobel prizes so that's the highest you can get uh didn't know in the 50s 60s they were pondering over this question and then it came as a sort of surprise I think at the time that's what people told me they're still alive you know uh so it came as a bit of a surprise initially that this is possible I'm just trying to talk it up a bit so you appreciate maybe it now it's it's a decade old result and uh everybody's just shrugging their shoulders of course it is possible but maybe it's not so obvious um we can we can pick our our pivot more carefully and then we get worst case linear time but to do to do that you have to be a bit careful so we'll work our way towards it first of all um what this what this weird spiral is trying to show you is a geometric Series right this is this is just showing that if you sum

16:13 up2 to the I starting at zero and up to Infinity that's the uh area that I drew here right we start with one then we have 1/2 then we add a quarter an eighth and so on and as you can see the arrangement of the Spiral always leaves enough space for the next little rectangle to go in there so the total area is is two and it converges to two if you keep going that's just uh Elementary um uh stuff so I just like the picture sorry for that so if if we somehow can guarantee that um right I should probably connect this to Quick select why is why is this relevant

17:02 now let's do this in the code what is the cost of of this code uh choosing the pivot at least the way we've done it before wasn't very expensive the key point was that the partitioning method uses linear cost linear time and N here would be the the difference between those

17:29 two so so we pay linear time for doing the partitioning step that would be the first partitioning call and uh we multiply the whole thing by n so if I have an n in front here I get an N here I'm just multiplying it all by a factor n so if the first partitioning call has cost 1 time n uh it would give us the area of that box now if we somehow achieve magically this that the pivot is the exact median I'm starting with the entire list and I'm cutting it in half exactly so whichever way the recursion goes the the worst case is that I still have to look into half of the elements so the second partition call

18:37 we'll have 1 halftimes n the area and so that's what we add if you keep going like this if you always select the median no matter which way the recursion goes you will always have as the next cost something that's half of what we previously had so the total cost is summing up these powers of 1 12 * n and that sums up up to 2 * n which is which is Theta n that's linear that's great we like that so that means if we get a pivot that's uh close enough to the median we can do selection in linear time now the problem with this approach is H finding the median was the original problem or it could have been at least the whole problem was selecting by Rank and now I'm telling you oh fine it's it's solved if you give me the exact median but that's the original problem so it it seems

19:37 useless it isn't useless because we don't actually need an exact median so we can do something more fuzzy uh more concretely if you if you fix some um some small number Epsilon so some some constant number say I don't know Epsilon is

20:03 0.01 it's enough if our pivot is in this range it just shouldn't be too much extreme uh it shouldn't be too close to either of the end points and the way to show this is is using the same kind of argument you start with the full array now in the worst case your pivot is right here at the boundary of where it's allowed to be but you still lose this Epsilon n elements and you recurse on something of size one time Epsilon n here you again split off in the worst case at least these Epsilon n elements so what you recurse on is 1 minus Epsilon squar n elements so if you keep summing that

21:00 up now the actual algorithm would never go to Infinity it would stop at some point after at most end steps it has to stop but we can upper bound that standard trick we can say instead of bothering with this upper bound here I'll just be more generous and go all the way up to

21:50 Epsilon so if we pick our Epsilon very small this is 100n uh is a bit bigger than 2N but it's still linear at least if we can somehow guarantee that this is a constant fraction away from the end points okay is there a question so you have to

22:21 what hashing or caching caching caching I don't see how you can use caching uh let's let's let's talk afterwards uh it's it's not I don't I don't hear well uh in the distance and maybe it takes us too far away um I don't see how you would use

22:56 caching so the the partitioning you do is different each time I don't I don't think you can remember much let's discuss it afterwards uh I don't think it's it's effective use of the time um it's better one-on one let me show you the solution which again um it looks a bit messy but it fits on one slide so uh uh it's it's manageable

23:20 Median of medians algorithm

23:30 complexity but remember again celebrated by famous people at the time um the way to choose the pivot is to use the algorithm recursively in a tricky way so where we choose our pivot here we call this function and um what it does in uh conceptually is uh you have your your array of of all the

24:06 elements I probably need more but yeah um you take groups of five and find the median of those five so uh say this is the one and then you keep this guy separate in the front then you take the next five elements H it's a tiny example so yeah we'll only get these

24:36 two so you take groups of five that's what this does uh we can be generous it's it's a small thing so we just sort that entirely and then we take the middle element that's the median of those five and we move that to the beginning of the array so once we're done we'll have the first fifth filled with all those

25:02 uh and the rest is well sorted groups of four but we'll actually ignore that now to find the pivot we take the exact median of those five ele of these uh the medians of five so in this case it's it's five elements but that's kind of a stupid coincidence let's make my example a little

25:28 bigger okay so this is just a fifth of all elements but we recursively call our algorithm on this once we come back with that pivot the rest is as in quick select no changes the only change is that uh I renamed the method and um a few things to point out first of all we do two recursive calls to the function but from two different places so these are two mutually recursive functions this one calls itself recursively but it also calls this function which again calls that one so it's a bit of a messy uh messy relationship but you can do this U standard practice but it means we we essentially have two recursive calls and uh remember that's potentially dangerous area danger danger uh Zone because that might mean we need time n log n not n uh for sorting we had two recursive calls and the overall time was and

26:36 login but we know that this uh innermost call is only on on a few elements only on one out of five the second recursive call um inside here is on the left or right part of the array after partitioning and we don't exactly know how big that is but we can give um a lower an upper bound on how big it can possibly be and that's what this picture tries to do so you have elements arranged in these groups of five that's what what this part does that arranges elements in groups of five and picks the median so the final the final pivot that we choose is this one that's what we uh what we get back here from that method call uh and what can we guarantee about this median it's bigger than all those elements and smaller than all those and each of those in turn has at least two above it that are smaller each of these has two that are below it that are bigger so transitively this pivot is bigger than at least all these elements in in this left upper blob and how many are there um

28:02 if you if you draw this to get to this number if you draw this a bit more abstractly and continuous the median is picked from the middle and then we have these five rows and basically we're looking at this part which is it looks like a quarter of this rectangle but it's actually more right because it's three out of five rows but half of the of the width so that's 3 over 10 of the overall

28:39 elements there are plus minus a few elements that you have to be more careful about if you want to rigorously prove this but for this part we'll we'll leave it with uh the asmic equivalent

28:56 statement right so again um this is length five in total the total rectangle here has length n over five then the black part that's n over 5/ two and the black part here is three you'll have to zoom in to read that so it's a if you multiply that out that's what you get

29:32 and then we can at least roughly upper bound the total time as follows we do a similar approach as for for merge sword back in the day where we said there's a recursive function C of n that gives us the cost of merge sword applied to n elements there's a a linear term that comes from the part from the partition remember it's not actually merge sword we're doing something closer to quick sword so so this part comes from the partition call and from these parts so we're sorting little parts of five elements each but we're doing this for the entire array that gives us some linear cost then we have two recursive calls this one is the one up here and the other one is the one down here either this one or this one we only have one of the two and we can upper bound how big the parts are that we recurse on for the blue one we we know exactly because it's it's every Fifth Element and for the orange one we know it's everything but this black part so all elements apart from 3 over 10 it's the same as 7/ 10 and now the this this next step don't do this in general it's it's only true because we can make the guess and then

31:05 prove it correct that the function is upper bounded by a constant times n but with that assumption we can pull these two together so instead of having two calls on two parts we do one call on the total size and that can only be uh more expensive if we do that and if you sum that up we get something like this and so we spend linear time but then we recurse on something that's a constant bit smaller so if you remember what we did before that's exactly the situation I I drew here except that our Epsilon is actually 0.1 not 0.01 so what we'll get as result will be 10 *

31:57 n and so that's how you get linear time for this that's the median of medians algorithm so it's a deterministic algorithm that always has linear time uh worst case cost for finding any rank in in an

32:14 array as part of the more sophisticated dividing conquer algorithms so you don't need to you don't need to know the analysis in more detail than what I showed here there's there's two places where uh to make that formal needs needs um needs a bit more work um and I don't want to do that here so you only need to know it at this level and I think if you you roughly know how the picture works you'll be good I mostly want to keep keep the knowledge that there is a deterministic selection algorithm with