Video 2-16: Recap Median-of-medians

0:04 Then last time I already introduced the problem that we'll first look at even though it looks like it's not connected at all with this question of deferred data structures. It will turn out to be a useful lower bound to compare with. And that's this problem of multiple selection.

0:23 Um what's widely known, I guess, is selection by rank, something like finding the median in a list of unsorted elements. Um I'll I'll recap this in a second, but you could do this in linear time uh even deterministically. Uh multiple selection is a little less well known. Um I'll change that, though. So, the input here is uh again um a sequence or an array of unsorted elements. Um but now we also get a whole collection of ranks that we're trying to find. Or you could always reformulate these these selection by rank problems, you can always think of you uh rearrange the array so that afterwards at the positions that we that you're given, the element of the correct position has to be there. Or in other words, uh once you're done with the multiple selection call, there might be special ranks R1, R2, maybe adjacent R3, and maybe another one, R4. And then the rest is partitioned, so everything in here is less than R1, everything in here is between R1 and R2.

1:43 Okay, nobody can read this. Uh also, it's not it's not quite right. Let me do it again properly. So, if this is an array, then the elements in this range are all less or equal A at this position R1.

2:01 The elements in between here are between AR1 and R2 and so forth. So, it's partitioned in the quicksort sense as if you had started running quicksort, but then lost interest and left it after [snorts] finding precisely these pivots.

2:29 That's essentially equivalent because for an algorithm to be correct in identifying the elements of these ranks it effectively has to learn how all the other elements relate to the elements of the query ranks. If it somehow didn't acquire that knowledge, you could modify the input in a style of an adversary argument and the algorithm would report an incorrect result. Right, if it doesn't learn how precisely every element relates to the other ranks, you could change the input so that at that element is different and then the reported elements have a different rank, so they wouldn't be the ones you were trying to find.

3:14 Here's a concrete example of this could look like. You're given an unsorted list and some ranks. You could pretend or imagine that you completely sort the array and that gives you the elements that you're supposed to return, namely here the ones at these ranks. And we want to report these in sorted order but we don't want to sort the entire array. We want to just find out where who these elements are without spending n log n time to sort the entire array.

3:47 All right. Uh First, let's recap algorithms for this simple problem for a single selection. I expect that most people will have seen this, but let me maybe uh briefly explain how it works. Uh I will expect that people have seen quick select, which is essentially this algorithm where instead of this clever uh recursive and mutually recursive call here, if you replace this by just selecting some random element as a pivot, then it's quick select.

4:42 And quick select just says uh um pick a random pivot, partition the array around this element, so everything smaller than the pivot goes left, everything larger than the pivot goes right. So, let's say the pivot was this element. That's our B. Then this is all smaller than A of B. And this is larger than A of B. That's what partition is supposed to do. Again, I'm I assume that you've seen this before, how to do partition, etc. I'm just uh recapping what it does because we'll build on that later. Um you can many many different ways how to do this in more or less smart ways. Uh the probably fastest in practice is to have two pointers from opposite ends that walk along the array and as uh when they find something that's on the wrong side, they stop, wait for the other, and then you do one swap, and you continue. That's all um basic basic components of quick sort and quick select.

5:47 After that partitioning step, you know that this element, the pivot, is at the final position where it would have been if you entirely sort the array. Or well, it stay where where it will stay if you were to continue sorting with quick sort. Now, we don't do that, but if the element if the position of the pivot, which lands at position J in the end, uh I should probably say J here. Because B um B is an initial position in the array, but it might be moved around, so let's not rely on this staying in the same place.

6:28 If at the end J is the rank that you're trying to find, the parameter was called with, then we're happy. Then we found an element that is in this position, and we could just return it. That's the lucky case. If that happens early on, then we can terminate right away. The typical case is that we're either too small or too big. And in that case, say uh the element that we're looking for is larger than J, the rank is larger than J, then we have to keep looking in this right half. And so, we do so recursively. Call ourselves on the right side and the same position in the array. Otherwise, we call ourselves on the left side. That was standard quick select. If you kind of ignore all up here, that's what quick select does. Now, quick select is fine in the average case or expected case if you pick random pivots, but it's not a good algorithm in the worst case because if you're unlucky, then uh each time you could pick a smallest or largest element as pivot, just get rid of one element and move further in.

7:33 If you're selecting, say, the middle, the median, and you always get unlucky, then you're looking at a quadratic running time overall. You can fix that by picking the pivot very carefully. And that's what's on the slide here. Who has seen median of medians? Who has not seen this? >> [snorts] >> Okay, cool. Then maybe let me explain. It's such a beautiful algorithm. Uh also, when this So, this is old, right? Um uh early '70s or so when this was published. I think at the time it came as a shock. People didn't really see or believe that this is um that this is possible. In hindsight, it's kind of trivial. Now, you can teach this as an undergrad's uh result. Um but uh uh that's always easier after the fact.

8:28 So, quick select is essentially fine if we had some guaranteed way to get a good pivot where we never get this extreme case of splitting just one element off or five elements off or something of that sort. So, we're trying to um select a pivot carefully, but we can't spend too much time because after all, the best pivot would be the median. But that's that's the darn problem we're trying to solve. We might select the median. So, we found a method to select the median if we're given the median. Uh well, yeah. See the problem? So, we [snorts] can't do that. But we can do something similar-ish. We find an element that is never too far away from the median, but with time that's cheaper than finding the exact one. And that's what this this business here is about. Um let me go to the uh figure here. This is part of the analysis, but you can also turn it into a description of the algorithm.

9:29 So, for the moment, ignore these little signs next to it. But just to explain what happens here, uh we group the elements into columns of five elements. So, these are indices 0 1 2 3 4 in the array, and then the next is 5 6 7 8 9, and so on. You take each of these columns of five elements and sort them. That's what has already happened here. Uh I guess my numbering is inconsistent with the uh less or equal signs. I think it's more natural to sort ascendingly.

10:22 So, let's pretend that's the indices. So, we fill the columns from top to bottom. Now, each column is sorted, and that is cheap because it's just five elements. So, I do all of these sorting steps of five elements each, that is linear time. It con- takes constant time for five elements, and I do this n over five times.

10:54 Now, uh from all these columns of five elements, I'm going to take the middle ones. And again, ignore the red part for now. I'll come back to that. What the algorithm does is just take the middle ones, and a convenient way is to swap the middle ones to the left. So, after that, these guys are compactly sitting in the first fifth of the array. n over five These are all the middle guys from these columns, and then the other elements are sitting here in the right part.

11:38 Now, I'm recursively calling my original algorithm on this prefix M was this M of N over 5. I'm recursively calling myself on this one to find the median among those middle elements.

11:55 And that's why the algorithm is called median of medians because each of these is the median of five elements and I'm giving the overall median of all the medians. And that thing, what I get back from that, is what I use as pivot in the original algorithm.

12:14 So, look at the monster we've created. This is a mutually recursive algorithm because this one calls this and this one calls this. And in particular, I do over the course of this, I do essentially two recursive calls. Whereas quick select had just one. Now, luckily this first recursive call is relatively small. It's always on only a a fifth of the elements. And for the second recursive call, here's my picture again. We can guarantee that it's it's only going to look at uh seven 70% of the elements. At least 30% are excluded.

12:54 And for for this to see this um you need to look at what this pivot element and how it is chosen. Uh this is a little P. This that's the actual pivot we use. It is the median of all the medians. So, all these to the left here are smaller than the pivot. They're not not sorted, but less than P, right? This is less than P, less than P, less than P. Now, everything above in this column is less than this guy. So, by transitivity, these are all smaller than the pivot. And so, that is for essentially half the columns, three elements each. That's why you get this uh uh m half times three for up here. That is uh the elements that are guaranteed to be smaller than the pivot. Uh we don't know in which side we recurse, so we need a symmetric bound for the elements larger than the pivot, that's the guys up here or down here.

13:55 It's the same argument. Uh the pivot is smaller than these, and this is smaller than these, so these are all bigger than the pivot. So, no matter where um exactly we recurse, there's always going to be 30% of the elements that are gone after this recursive call. That's the important part. All right. Uh and then you can finish off the analysis with a recurrence. The total cost of of applying this algorithm on n total elements is some linear cost, this is for partitioning mostly, and also for the sorting of the columns. Then we have one recursive call on a fifth of the elements, and one recursive call on at most 7/10 of the elements. And now comes a clever trick that you can also do more rigorously, but uh to use the the lovely German German loanword Ansatz, you guess the solution, and you verify that that solution satisfies the recurrence. Uh and in particular here, um if the overall cost is linear, then these two terms are upper bounded by the cost of light to the sum inside.

15:10 Uh for the experts in um uh in recurrences, there's a cool uh Roura's discrete master theorem that can directly you out on based on this recurrence what the result is. That's another option. Or you do this kind of little mathematical magic trick. Now, a fifth and 7/10 adds up to 9/10, which is famously less than one. So, what this recurrence means is that after paying a linear cost, we reduced the input to something that's constant factor smaller. Which means this whole thing is a geometric series and the overall cost is linear. The constant for the for this algorithm isn't so great because it only gets In the worst case, it gets rid of just 10% of the elements. And we do a lot of uh uh effort to get there. But it is deterministic guaranteed linear time in uh for for any selection that we want to do. Okay. Questions to this point? I didn't want to go into this so much.

16:22 Uh this is not part of the of the part that follows on. You can essentially treat it as a black box. There is a way in linear time to select any such rank. Uh but I think it's such a cool algorithm. >> [snorts] >> I might as well recap. Yeah.

16:48 Does this suit well suit work well for parallel? Some parts, yes. Uh I mean, all these sorting steps you can do in parallel. Partitioning can be parallelized if you're a bit clever. Uh the recursive calls are kind of independent.

17:05 But not entirely, right? They don't They're are not on disjoint parts. So, you have to wait for this one to come back before you can continue. So, maybe it's not the perfect method. Uh it should it should get some speed up. But you you'll have to um use a synchronization point after this first recursive call. Not great. But yeah, if you can manage to par- parallelize the partitioning step, it should do okay.