0:00

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.

Â 4:16

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.

Â 7:35

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.

Â