So let's review this story so far. We've been discussing the quick sort algorithm,
here again is its high level description. So quick sort you call two subroutines
first and then you make two recursive calls. So the first subroutine,
ChoosePivot , we haven't discussed yet at all. That will be one of the main topics of this video.
But the job of the choose pivot subroutine is to somehow select one
of the N elements in the input array to act as a pivot element. Now, what does it
mean to be a pivot? Well, that comes into play in the second subroutine. The
partition subroutine, which we did discuss quite a bit in a previous video. So what
partition does is it rearranges the elements in the input array, so that it
has the following property. So that the pivot P winds up in its rightful position.
That is, it's to the right of all of the elements less than it. And it's to the
left of all of the elements bigger than it. The stuff less than it's to the left
in some jumbled order. The stuff bigger than it is to the right in some jumbled
order. That's what's listed here as the first part and the second part of the
partitioned array. Now, once you've done this partitioning you're good to go. You
just recursively solve recursively sort the first part. After you get them in the
right order, you call Quick Sort again and recursively sort the right part. And,
bingo, the entire array is sorted. You don't need to combine step. You don't need
a [inaudible] step. Moreover, recall in a previous video we saw that the partition
array can be implemented in linear time and, moreover, it works in place with
essentially, no additional storage. We, also, in an optional video formally
prove the correctness of Quick Sort. And remember, QuickSort is independent of how
you implement the ChoosePivot subroutine. So what we're going to do now is discuss
the running time of the QuickSort algorithm. And this is where the choice of
the pivot is very important.
So what everybody should be wondering about at
this point is, "Is Quick Sort a good algorithm? Does it run fast?" The bar is
pretty high. We already have MergeSort, which is a very excellent, practical, n
log n algorithm. [sound] The key point to realize at this juncture is that we are
not currently in a position to discuss the running time of the quick sort algorithm,
the reason is we do not have enough information. The running time of the quick
sort depends crucially on how you choose the pivot. It depends crucially on the
quality of the pivot chosen.
You'd be right to wonder what I mean by a pivot's quality. And basiclaly what I mean is
pivot is good if it splits the partitioned
array into roughly two equal-sized subproblems. And it's bad, it's of low
quality if we get very unbalanced subproblems. So to understand both what I
mean and the ramifications of having good-quality and bad-quality pivots, let's
walk through a couple of quiz questions. This first quiz, quiz question is meant to
explore a sort of worst case execution of the quick sort algorithm. What happens
when you choose pivots that are very poorly suited for the particular input
array. Let me be more specific. Suppose we use the most naive choose pivot
implementation like we were discussing in the partition video. So, remember, here we
just pluck out the first element of the array and we use that as the pivot. So
suppose that's how we implement the choose pivot subroutine, and moreover, suppose
that the input array to quicksort is an array that's already in sorted order. So,
for example, if we just have the numbers one through eight, it would be one, two,
three, four, five, six, seven, eight, in order. My question for you is, what is the
running time of this recursive quicksort algorithm on an already sorted array if
we always use the first element of a subarray as the pivot? Okay so this is a
slightly tricky, but actually a very important question. So the answer is the
fourth one. So it turns out that quick sort, if you pass it an already sorted
array and you're using the first element as pivot elements, it runs in quadratic
time. And remember, for a sorting algorithm, quadratic is bad. It's bad in
the sense that we can do better. Merge short runs in time n log n, which is
much better that n-squared, and if we are happy with an n-squared running time, we
wouldn't have to resort to these sort of relatively exotic sorting algorithms. We
could just use insertion sort and we'd be fine, we'd get that same quadratic running
time. Okay so now I owe you an explanation. Why is it that QuickSort
can actually run in quadratic time in this unlucky case of being passed already
sorted input array. Well, to understand, let's think about what pivot gets chosen
and what are the ramifications of that pivot choice for how the array gets
partitioned, and then what the recursion looks like. So. Let's just think of the
array as being the numbers one through n in sorted order. What is gonna be our
pivot? Well, by definition we're choosing the first element of the pivot, so the
pivot is just gonna be one. Now we're going to invoke the partition subroutine
and if you go back to the pseudo code of the partition's subroutine, you'll notice
that if you pass in an already sorted array, it's gonna do essentially nothing.
It's just gonna advance the n [inaudible] and j until it falls off the end of the
array. And it's just going to return back to us the same array that it was pathed as
input. So, partitioned subroutine is given an already sorted array, returns an
already sorted array. Okay? So we have just a pivot one in the first position and
then the numbers two through n in order in the remainder of the positions. So if we
draw our usual picture of what a, partitioned array looks like, with
everything, less than the pivot, to the left, everything bigger than the pivot, to
the right. Well, since nothing is less than the pivot, this stuff is going to be
empty. This will not exist, and to the right of the pivot, this will have length,
N minus one, and moreover it will still be sorted. So once partition completes, we go
back to the outer call of quick sort, which then calls itself recursively twice.
Now in this case, one of the recursive calls is just vacuous. There's just an
empty array. There's nothing to do. So really there's only one recursive call,
and that happens on a problem of size only one less. So this is about the most
unbalanced split we could possibly see. Right? Where one side has zero elements,
one side's N minus one. That's not really good any worse than that. And this
is going to keep happening over and over and over again. We're gonna recurse on the
numbers two through n. We're gonna choose the first element, the two as the pivot.
Again, we'll feed it to partition, we'll get back the exact same subarray that we
handed it in, we get to the numbers two through n in sorted order. We exclude the
pivot two. We recourse on the numbers three through n, a subarray of length n -
two. The next recursion level, we recurse on an array of size, of length n - three,
then n - four, then n - five, and so on, until finally, after [inaudible] a
recursion depth of n roughly, we got down to just the last element. N, the base case
kicks in and we return that and Quick Sort completes. So that's how Quick Sort is
gonna execute on this particular input with these particular pivot choices, so
what running time does that give to us? Well. The first observation is that, you
know in each recursive call we do have to invoke the partition at sub-routine, and
the partition sub-routine does look at, every element in the array it is passed as
input. So if we pass partition in array of like K, it's gonna do at least K
operations Cuz it looks at each element at least once. So the run time is going to be
bounded below, by the work we do on the outermost call, which is on an array of
like M. Plus the amount we do in the second level of recursion, which is on a
subarray of length n - one, plus n - two, plus blah, blah, blah, blah, blah, all the
way down to plus one for the very last level of recursion. So this is a lower ban
on our running time and this is already theta of n squared. So one easy way to see
why this sum, N+N-1+ etcetera, etcetera, leads to a bound of N squared, [inaudible]
just focus on the first half of the terms. So the first N over two terms in the sum
are all of magnitude at least N over two. So the sums at least N squared over four.
It's also evident that this sum is at most, N squared. So, overall, the running
time of Quick Sort on this bad input is going to be quadratic. Now having
understood what the worst case performance the Quick Sort algorithm is, let's move on
to discuss its best case running time. Now we don't generally care about the best
case performance of algorithms for its own case, the reason that we wanna think about
Quick Sort in the best case, first of all it'll give us better intuition for how the
algorithm works, second of all it will draw a line in the sand. Its average case
running time certainly can't be better than the best case so this will give us a
target for what we're shooting for in our subsequent mathematical analysis. So what
with the best case, what is the highest quality pivot we could hope for, well
again. We think of the quality of a pivot as the amount of balance that it provides
between the two subproblems. So ideally, we choose a pivot which gave us two
subproblems, both of size n/2 or less. And there's a name for the. Element that would
give us that perfectly balanced split. It's the median element of the array,
okay? The element where exactly half of the elements are less than it and half of
the elements are bigger than it. That would give us essentially perfect 50/50
split of the input array. So here's the question. Suppose we had some input and we
ran quicksort and everything just worked out in our favor in the, magically in the
best possible way. That is, in every single recursive indication of quicksort
on any sub-array of the original input array, suppose we happen. To get as our
pivot the median element. That is, suppose in every single recursive call we wind up
getting a perfect 50, 50 split of the input array before we recurse. This
question asks you to analyze the running time of this algorithm in this magical
best case scenario. So the answer to this third to this question is the third
option. The answer is it runs in n log n time. Why is that? Well, the reason is
that then the recurrence which governs the running time of quicksort is, exactly
matches the recurrence that governs the merge sort running time, which we already
know is n log n. That is, the running time Quick Sort requires, in this magical,
special case, on an array of like N well, as usual you have a recurrence in two
parts. There is the work that gets done by the recursive calls and there is the work
that gets done now. Now by assumption, we wind up picking the Median as the Pivot.
So there's going to be two recursive calls, each of which will be on
[inaudible] input of size of most and over two, and we can write this. This is
because the Pivot equals the Mid-Median. So this is not true for quicksort in
general. It's only true in this magical case where the pivot is the median. So
that's what's gets done by the two recursive calls, and then how much work do
we do outside of the recursive calls? Well, we have to do the choose pivot
subroutine, and I guess strictly speaking I haven't said how that was implemented,
but let's assume that choose pivot does only a linear amount of work. And then as
we've seen, the partition subroutine only does a linear amount of work as well. So
let's say oh then, for work outside of the recursive calls. And what do we know? We
know this implies [inaudible] using the master method or just by using the exact
same argument as from [inaudible]. This gives us a running time bound of N log in.
Then again something I haven't really been emphasizing but which is true is that
actually we can write. Theta of N log N. And that's because, in the recurrence, in
fact, we know that the work done outside of the recursive calls is exactly theta of
N, okay? Partition needs really linear time, not just big O of N time. In fact,
the work done outside of the recursive calls is theta of N. That's because the
partition subroutine does indeed look at every entry in the array that it's passed.
And as a result, we didn't really discuss this so much in the master method. But as
I mentioned in passing, if you have recurrences which are tight in this sense,
then the, the results of the master method, can also be strengthened to be
theta instead of just big O. But those are just some extra details. The upshot of
this quiz is that even in the best case, even if we magically get perfect pivots
throughout the entire trajectory of quicksort, the best we can hope for is an
n log n upper bound. It's not gonna get any better than that. So the question is,
how do we have a principled way of choosing pivots so that we get this best
case, or something like it that's best case n log n running time? So that's what
that problem that we have to solve next. So the last couple quizzes have identified
a super important question as far as the implementation of Quick Sort, which is how
are we going to choose these pivots, right. We now know they have a big
influence on the running time of our algorithm. It could be as bad as N squared
or as good as N log N. We really want to be on the N log N side. So key question.
How to choose pivots. [sound] And quicksort is the first killer application
we're going to see of the idea of randomized algorithms, that is, allowing
your algorithms to flip coins in the code so that you get some kind of good
performance on average. So the big idea. Is random [sound] pivots. By which I mean.
For every time we recursively call quick sort and we are passed some sub-array of
length k. Among the k candidate pivot elements in the subarray, we're going to
choose each one with eq, equally likely. With probability of one over K, and we're
gonna make a new random choice every time we have a recursive call. And then we're
just gonna see how the algorithm does. So this is our first example of a randomized
algorithm. This is an algorithm, where, if you feed it exactly the same input, it
will actually run differently on different executions. And that?s ?cause there's
randomness internal to the code of the algorithm. Now, it's not necessarily
intuitive that randomization should have any purpose in computation, in software
design and algorithm design. But, in fact, and this has been sort of one of the real
breakthroughs in algorithm design. Mostly in the'70s, realizing how important this
is. That the use of randomization can make algorithms more elegant. Simpler, easer to
code, more faster. Or just simply you can solve problems that you could not solve,
at least not solve as easily without the use of randomization so it's really one
thing that should be in your toolbox as an algorithm designer, randomization. Quick
Sort will be the first kill, killer application but we'll see a couple more
later in the course. Now, by the end of this sequence of videos, I'll have given
you a complete, rigorous argument about why this works. Why with random pivots,
quicksort always runs very quickly on average. But, you know, before we begin to
say anything too formal, let's develop a little bit of. Intuition, or at least kind
of a daydream, about why on earth could this possibly work. Why on earth could
this possibly be a good idea, to have randomness internal to our quicksort
implementation. Well, so first just, you know, very high level. What would be sort
of the hope or the dream? The hope would be, you know, random pivots are not gonna
be perfect. I mean, you're not gonna just sort of guess the median. You only have a
one in n chance of figuring out which one the median is. But the hope is that most
choices of a pivot will be good enough. So that's pretty fuzzy. Let's drill down a
little bit and develop this intuition further. Let me describe it in two steps.
[sound] The first claim is that, you know in our last quiz we said suppose we get
lucky and we always pick the median in every single recursive call. We observed
we'd do great. We'd get enlogin running time. So now let?s observe that actually
to get the enlogin running time that it's not important that we magically get the
median every single recursive call. If we get any kind of reasonable pivot by which
a pivot that gives us some kind of approximately balanced split of the
problems again, we are gonna be good. So the last quiz really wasn't particular to
getting the exact median. Near medians are also fine. To be concrete, suppose we
always pick a pivot which guarantees us a split of 25 to 75 or better. That is both
recursive calls should be called on a raise of size. And most 75 percent of the
one that we started with. So precisely, if we always get a 25/75 split or better in
every recursive call. I claim that the running time of Quick Sort in that event
will be Big O of N log N. Just like it was in the last quiz where we were, we were
actually assuming something much stronger, that we were getting the median. Now this
is not so obvious, the fact that 25/75 splits guarantee N log N running time. For
those of you that are feeling keen, you might wanna try to prove this. You can
prove this using a recursion tree argument. But because you don't have
balanced subproblems, you have to work a little bit harder than you do in the cases
covered by the master method. So that's the first part of the intuition. And this
is what we mean by [inaudible] being good enough. If we get a 25/75 split or better,
we're good to go. If we get our desired, our target N log N running time. So the
second part of the intuition is to realize that, actually, we don't have to get all
that lucky to just be getting a 25/75 split. That's actually a pretty modest
goal. And even this modest goal is enough to get the N log N running time. Right? So
suppose our array contains the numbers, the integers between one and 100, so it's
an array of length 100. Think for a second, which of those elements is gonna
give us a split? That's 25, 75, or better. So if we pick any element between 26 and
75. Inclusive. Will be totally good. Right. We pick something that's at least
26. That means that the left subproblem is going to have at least the elements one
through 25. That'll even have at least 25 percent of the elements. If we pick
something less than 75, then the right subproblem will have all of the elements
76 through 100 after we partition. So, we'll also have at least 25 percent of the
elements. So anything between 26 and 75 gives us a 75, 25 split or better. But
that's a full half of the elements. So it's as good as just flipping one
[inaudible] fair coin and hoping we get heads. So with 50 percent probability, we
get a split good enough to get the. Isn't enough to get this N log inbound. And so,
again, the high level hope is that often enough, you know, half of the time, we get
these you know, good enough splits. 25, 75 splits or better. So, that would soon
suggest and end log and running time of average is a legitimate hope. So thats the
hell of a intuition, but if I were you I would certainly not be content with this
somewhat hand wavy explanation that I've given you so far. What I've told you is
sort of the hope, the dream, why there is at least a chance, this might work. But,
but the question remains, and I would encourage such skepticism, which is, does
this really work. And to answer that we're gonna have to do some actual mathematical
analysis and that's what I am gonna show you. I am gonna show you complete vigorous
analysis of the quick sword algorithm with random pivots and we'll show that yes in
fact it does really work. And this highlights what's gonna be a recurring
theme in this course and a recurring theme in this just study and understanding of
algorithm which is quite often there's some fundamental problem we are trying to
go to the solution and you come up with a novel idea. It might be brilliant. And it
might suck, and you have no idea. Now obviously you can cut up the idea, run it
on some concrete instances, and get a feel for you know, whether it seems like a good
idea or not, but if you really wanna know fundamentally what makes the idea good or
what makes the idea bad, really you need to turn to mathematical analysis to give
you a complete explanation. And that's exactly what we're going to do with Quick
Sort and then we'll explain in a very deep way why it works so well. Specifically, in
the next sequence of three videos, I'm going to show you an analysis, a proof of
the following theorem about quicksort. So under no assumptions about the data, that
is for every input array of a given length, say n, the average running time. A
quick sort implemented with random pivots is [inaudible] than log in. And again, In
fact it's theta and then log in, but we'll just focus on the big O of N log in part.
So this is a very, very cool theorem about this randomized Quick Sort algorithm. One
thing I wanna be clear so that you don't undersell this guarantee in your own mind,
this is a worst case guarantee with respect to the input. If you'll notice at
the beginning of this theorem, what do we say, for every input array of linked in.
Alright so we have absolutely no assumptions about the data so this is a
totally and general purpose sorting subroutine which you can use whenever you
want even if you have no idea where the data's coming from and these guarantees
are still going to be true. This of course is something I held forth about at some
length back in our Guiding Principles video. When I argued that, if you can get
away with it, what you really want is general purpose algorithms which make no
data assumptions so they can be used over and over again in all kinds of different
contexts and it still have guarantees, and quicksort is one of those. So, basically,
if you have a dataset and it fits in the main memory of your machine, again,
sorting is a for free subroutine. In particular, quicksort the quicksort
implementation is for free. So, this runs so blazingly fast. It doesn't matter what
the array is. Maybe you don't even know why you want to sort it but go on ahead.
Why not? Maybe it'll make your life easier like it did, for example, in the clo.
[inaudible] Payout rhythm for those of you that watched those two optional videos.
Now, the word average does appear in this theorem. And, you know, as I've been
harping on this, average is not over any assumptions on the data. We're certainly
not assuming that the input array is random in any sense. The input array can
be anything. So where is the averaging coming from? The averaging is coming only
from randomness, which is internal to our algorithm. Randomness that we put in the
code ourselves, that we're responsible for. So remember, randomized algorithms
have the interesting property that, even if you run it on the same input over and
over again, you're gonna get different executions. So the running time of a
randomized algorithm depend-, you know, can vary as you run it on the same input
over and over again. The quizzes have taught us that the running time of Quick
Sort on a given input fluctuates from, anywhere between the best case of N log N
to the worst case of N squared. So what this theorem is telling us is that, for
every possible input array. While the running time does indeed fluctuate between
an upper bound of N squared, and the lower bound of N log N. The best case is
dominating. On average, it's N log N. On average, it's almost as good as the best
case. That's what's so amazing about Quick Sort. [inaudible] N squared that can pop
up once in a while, has, it doesn't matter. You're never gonna see it. You're
always gonna see this N log N like behavior in randomized quick sort. So, for
some of you, I'll see you next in a video on probability review, that's optional.
For the rest of you, I'll see you in the analysis of this theorem.