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.