So now we come to one of my favorite sequence of lectures, where we going to discuss the famous QuickSort algorithm. If you ask professional computer scientists and professional programmers to draw up a list of their top five, top ten favorite algorithms, I'll bet you'd see QuickSort on many of those, those peoples' lists. So, why is that? After all, we've already discussed sorting. We already have a quite good and practical sorting algorithm, mainly the Merge Sort algorithm. Well, QuickSort, in addition to being very practical, it's competitive with, and often superior to, Merge Sort. So, in addition to being very practical, and used all the time in the real world, and in programming libraries, it's just a extremely elegant algorithm. When you see the code, it's just so succinct. It's so elegant, you just sorta wish you had come up with it yourself. Moreover, the mathematical analysis which explains why QuickSort runs so fast, and that mathematical analysis, we'll cover in detail, is very slick. So it's something I can cover in just about half an hour or so. So more precisely what we'll prove about the QuickSort algorithm is that a suitable randomized implementation runs in time N log N on average. And I'll tell you exactly what I mean by on average, later on in this sequence of lectures. And, moreover, the constants hidden in the Big-Oh notation are extremely small. And, that'll be evident from the analysis that we do. Finally, and this is one thing that differentiates QuickSort from the merge sort algorithm, is it operates in place. That is, it needs very little additional storage, beyond what's given in the input array, in order to accomplish the goal of sorting. Essentially, what QuickSort does is just repeated swaps within the space of the input array, until it finally concludes with a sorted version of the given array. The final thing I want to mention on this first slide is that, unlike most of the videos, this set of the videos will actually have an accompanying set of lecture notes, which I've posted on, in PDF, from the course website. Those are largely, redundant. They're optional, but if you want another treatment of what I'm gonna discuss, a written treatment, I encourage you to look at the lecture notes, on the course website. So, for the rest of this video, I'm gonna give you an overview of the ingredients of QuickSort, and what we have to discuss in more detail, and the rest of the lectures will give details of the implementation, as well as the mathematical analysis. So let's begin by recalling the sorting problem. This is exactly the same problem we discussed back when we covered Merge Sort. So we're given as input an array of n numbers in arbitrary order. So, for example, perhaps the input looks like this array here. And then what do we gotta do? We just gotta output a version of these same numbers but in increasing order. Like when we discussed Merge Sort, I'm gonna make a simplifying assumption just to keep the lectures as simple as possible. Namely I'm going to assume the input array has no duplicates. That is, all of the entries are distinct. And like with the merge sort, I encourage you to think about how you would alter the implementation of QuickSort so that it deals correctly with ties, with duplicate entries. To discuss how QuickSort works at a high-level, I need to introduce you to the key subroutine, and this is really the, key great idea in QuickSort, which is to use a subroutine which partitions the array around a pivot element. So what does this mean? Well, the first thing you gotta do is, you gotta pick one element in your array to act as a pivot element. Now eventually we'll worry quite a bit about exactly how we choose this magical pivot element. But for now you can just think of it that we pluck out the very first element in the array to act as the pivot. So, for example, in the input array that I mentioned on the previous slide, we could just use "3" as the pivot element. After you've chosen a pivot element, you then re-arrange the array, and re-arrange it so that every, all the elements which come to the left of the pivot element are less than the pivot, and all the elements which come after the pivot element are greater than the pivot. So for example, given this input array, one legitimate way to rearrange it, so that this holds, is the following. Perhaps in the first two entries, we have the 2 and the 1. Then comes the pivot element. And then comes the elements 4 through 8 in some perhaps jingled order. So notice that the elements to the left of the pivot, the 2 and the 1, are indeed less than the pivot, which is 3. And the five elements to the right of the pivot, to the right of the 3, are indeed all greater than 3. Notice in the Partition subroutine, we do not insist that we get the relative order correct amongst those elements less than the pivot, or amongst those elements bigger than the pivot. So, in some sense, we're doing some kind of partial sorting. We're just bucketing the elements of the array into one bucket, those less than the pivot, and then a second bucket, those bigger than the pivot. And we don't care about, getting right the order amongst each, within each of those two buckets. So, partitioning is certainly a more modest goal than sorting, but it does make progress toward sorting. In particular, the pivot element itself winds up in its rightful position. That is, the pivot element winds up where it should be in the final sorted version of the array. You'll notice in the example, we chose as the pivot the third largest element, and it does, indeed, wind up in the third position of the array. So, more generally, where should the pivot be in the final sorted version? Well, it should be to the right of everything less than it. It should be to the left of everything bigger than it. And that's exactly what partitioning does, by definition. So, why is it such a good idea to have a partitioning subroutine? After all, we don't really care about partitioning. What we want to do is sort. Well, the point is that partitioning can be done quickly. It can be done in linear time. And it's a way of making progress toward having a sorted version of an array. And it's gonna enable a divide-and-conquer approach toward sorting the input array. So, in a little bit more detail, let me tell you about two cool facts about the Partition subroutine. I'm not gonna give you the code for partitioning here. I'm gonna give it to you on the next video. But, here are the two salient properties of the Partition subroutine, discussed in detail in the next video. So the first cool fact is that it can be implemented in linear, that, is O(N) time, where N is the size of the input array, and moreover, not just linear time but linear time with essentially no extra overhead. So we're gonna get a linear time of mutation, where all you do is repeated swaps. You do not allocate any additional memory. And that's key to the practical performance of the QuickSort algorithm. [sound] Secondly, it cuts down the problem size, so it enables the divide-and-conquer approach. Namely, after we've partitioned an array around some pivot elements, all we have to do is recursively sort the elements that lie on the left of the pivot. And recursively sort the elements that lie on the right of the pivot. And then, we'll be done. So, that leads us to the high-level description of the QuickSort algorithm. Before I give the high-level description, I should mention that this, algorithm was discovered by, Tony Hoare, roughly, 1961 or so. This was at the very beginning of Hoare's career. He was just about 26, 27 years old. He went on to do a lot of other contributions, and, eventually wound up winning the highest honor in computer science, the ACM Turing Award, in 1980. And when you see this code, I'll bet you feel like you wish you had come up with this yourself. It's hard not to be envious of the inventor of this very elegant QuickSort algorithm. So, just like in Merge Sort, this is gonna be a divide-and-conquer algorithm. So it takes an array of some length N, and if it's an array of length N, it's already sorted, and that's the base case and we can return. Otherwise we're gonna have two recursive calls. The big difference from Merge Sort is that, whereas in Merge Sort, we first split the array into pieces, recourse, and then combine the results, here, the recursive calls come last. So, the first thing we're going to do is choose a pivot element, then partition the array around that pivot element, and then do two recursive calls. And then, we'll be done. There will be no combined step, no merge step. So in the general case, the first thing you do is choose a pivot element. For the moment I'm going to be loose, leave the ChoosePivot subroutine unimplemented. There's going to be an interesting discussion about exactly how you should do this. For now, you just do it in some way, that for somehow you come up with one pivot element. For example, a naive way would be to just choose the first element. Then you invoke the Partition subroutine that we'll discuss in the last couple slides. [sound]. So recall that the results in a version of the array in which the pivot element p is in its rightful position, everything to the left of p is less than p, everything to the right of the pivot is bigger than the pivot, and then all you have to do to finish up is recurse on both sides. So let's call the elements less than p the first part of the partitioned array, and the elements greater than p the second part of the recursive array. And now we just call QuickSort again to recursively sort the first part, and then the, recursively sort the second part. And that is it. That is the entire QuickSort algorithm at the high-level. This is one of the relatively rare recursive, divide- and-conquer algorithms that you're going to see, where you literally do no work after solving the sub-problems. There is no combine step, no merge step. Once you've partitioned, you just sort the two sides and you're done. So that's the high- level description of the QuickSort algorithm. Let me give you a quick tour of what the rest of the video's going to be about. So first of all I owe you details on this Partition subroutine. I promise you it can be implemented in linear time with no additional memory. So I'll show you an implementation of that on the next video. We'll have a short video that formally proves correctness of the QuickSort algorithm. I think most of you will kinda see intuitively why it's correct. So, that's a video you can skip if you'd want. But if you do want to see what a formal proof of correctness for a divide-and-conquer algorithm looks like, you might want to check out that video. Then, we'll be discussing exactly how the pivot is chosen. It turns out the running time of QuickSort depends on what pivot you choose. So, we're gonna have to think carefully about that. Then, we'll introduce randomized QuickSort, which is where you choose a pivot element uniformly at random from the given array, hoping that a random pivot is going to be pretty good, sufficiently often. And then we'll give the mathematical analysis in three parts. We'll prove that the QuickSort algorithm runs in N log N time, with small constants, on average, for a randomly chosen pivot. In the first analysis video, I'll introduce a general decomposition principle of how you take a complicated random variable, break it into indicator random variables, and use linearity of expectation to get a relatively simple analysis. That's something we'll use a couple more times in the course. For example, when we study hashing. Then, we'll discuss sort of the key insight behind the QuickSort analysis, which is about understanding the probability that a given pair of elements gets compared at some point in the algorithm. That'll be the second part. And then there's going to be some mathematical computations just to sort of tie everything together and that will give us the bound the QuickSort running time. Another video that's available is a review of some basic probability concepts for those of you that are rusty, and they will be using in the analysis of QuickSort. Okay? So that's it for the overview, let's move on to the details.