I just got the number of divide and
conquer algorithms and, so far, I've been
short shrift to proofs of correctness.
This has been a conscience decision on my
part. Coming up with the right divide and
conquer algorithm for a problem can
definitely be difficult, but once you have
that eureka moment and you figure out the
right algorithm you tend to, also, have a
good understanding of why it's correct,
why it actually solves the problem on
every possible input. Similarly when I
present to you a divide and conquer
algorithm like, say, merge sort or
quicksort, I expect that many of you have
a good and accurate intuition about why
the algorithm is correct. In contrast the
running time of these developed
[inaudible] algorithms is often highly
non-obvious. So, correctness proofs for
divide-and-conquer algorithms tend to
simply formalize the intuition that you
have via a proof by induction. That's why
I haven't been spending much time on them.
But nevertheless, I do feel like I owe you
at least one rigorous correctness proof
for a divide-and-conquer algorithm, and we
may as well do it for quicksort. So in
this optional video, we'll briefly review
proofs by induction, and then we'll show
how such a proof can be used to rigorously
establish the correctness of quicksort.
The correctness proofs for most of the
other divide-and-conquer algorithms that
we discuss can be formalized in a similar
way. So let's begin by reviewing the
format for proofs by induction. So, the
canonical proofs by induction and the kind
that we'll be using here, is when you want
to establish an assertion for all of the
positive integers in. So now it's some
assertion which is parameterized by n,
where n is a positive integer. I know this
is a little abstract, so let me just be
concrete about the assertion that we
actually care about for quicksort. So for
us, the assertion P(n) is the statement
that cor, quicksort is always correct on
inputs of length n, arrays that have n
elements. So an induction proof has two
parts. The first part is a base case and
the second part is an inductive step. For
the base case you have to get started so
you show that at the very least your
assertion is true when n equals one. This
is often a trivial matter and that'll be
the case when we establish the correctness
of quick sort. Just on our rays with only
one element. So, the non-trivial part of a
proof by induction is usually the
inductive step. And in the inductive step,
you look at a value of n not covered by
the base case, so a value of n bigger than
one. And you show that if the assertion
holds for all smaller values, small
integers, then it also holds for the
integer n. That is, you show that for
every positive integer N that's two or
greater, you assume that P of K holds for
all K strictly less than N. And under that
assumption, which is called the inductive
hypothesis. Under the assumption that P of
K holds for all K strictly less than N,
you then establish that P of N holds as
well. So if you manage to complete both of
these steps, if you prove both the base
case that P(1) holds, you argue that
directly, and then also you argue that
assuming the inductive hypothesis, that
the assertion holds for all smaller
integers, it also holds for an arbitrary
integer n. Then you're done. Then in fact
you have proven that the assertion P then
holds for every single positive integer N.
Right? So for any given N that you care
about, the way you can derive that from
one and two is you just start from the
base case, P of one holds. Then you apply
the inductive step N minus one times. And
boom, you've got it. So you know that P
holds for the integer N that you care
about as well. And that's true for
arbitrarily large values of N. So those
are proofs by induction in general. Now
let's instantiate this proof format, this
type of proof for establishing the
correctness of quicksort. So let me write
again what is the assertion we care about.
Our definition of P(n) is gonna be that
quicksort is always correct on arrays of
length n. And of course what we want to
prove is that quicksort is correct no
matter what size array that you give it,
that is, we want to prove that P(n) holds
for every single n at least one. So this
is right in the wheelhouse of proofs by
induction. ?Kay, so that's how we're going
to establish it. Now depending on the
order in which you're watching the videos,
you may or may not have seen our
discussion about how you actually choose
the pivot, recall that the first thing
Quick Sort does is choose a pivot, then it
partitions the array around the pivot. So,
we're going establish the correctness of
Quick Sort, no matter how the choose pivot
sub-routine gets implemented. Okay, so now
matter how you choose pivots, you'll
always have correctness. As we, as we'll
see in a different video, the choice of
pivot definitely has an influence on the
running of Quick Sort, the correctness of
Quick Sort, there's no matter how you
choose the pivot. So it's perceived by a
proof by induction. So for the base case
when n equals one, this is a fairly
trivial statement. Right? So, then we're
just talking about inputs that have only
one element. Every such array is already
sorted. Quicksorts, in the bai, when n
equals one just returns the input array.
It doesn't do anything, and that is indeed
the sort of array that it returns. So, by
the rather trivial argument we had
directly proven that p of one holds. We've
proven the rather unimpressive statement
that quicksort always correctly sorts one
element arrays. Okay? No big deal. So,
let's move on to the inductive step. So in
the inductive step we have to fix an
arbitrary value of N that's at least two.
A value of N not covered by the base case.
So let's fix some value of N, that leaves
two. Now what are we trying to prove?
We're trying to prove that Quick Sort
always correctly sorts every input array
of length N. So we also have to fix an
arbitrary such input. So let's make sure
we're all clear on what it is we need to
show, what do you show in an inductive
step. Assuming that PFK holds. For all
smaller values, all smaller integers, then
P of N holds as well. And remember this is
the inductive hypothesis. So in the
context of quicksort, we're assuming that
quicksort never makes a mistake on any
input array that has length strictly
smaller than n. And now we just have to
show it never makes a mistake on array,
input arrays that have size exactly n. So
this is the point in the proof where we
actually delve into how Quick Sort is
implemented to argue correctness. So
recall what the first step of Quick Sort
is, it picks some pivot arbitrarily, we
don't know how, we don't care how. And
then it partitions the array around this
pivot element p. Now as we argued in the
video where we discussed the partition sub
routine, at the conclusion of that sub
routine, the array has been rearranged
into the following format. The pipit is
wherever it is, everything to the left of
the pipit is less than the pipit, and
everything bigger than the pipit is
greater than the pipit. Alright, this is
where how things stand at the conclusion
of the partitioning sub routine. So let's
call this stuff less than the pipit the
first part of the partition array, and the
stuff bigger than the pipit, the second
part of the partition array. And recall
our observation from the overview video
that the pivot winds up in its correct
position. Right, where would the pivot be?
Where is any element suppose to be in the
final sorted array? What's suppose to be
to the right of everything less than it,
and to the left of everything bigger than
it? And that's exactly where this
partitioning subroutine deposits the pivot
element peak. So now to imply the
inductive hypothesis, which you'll recall
is a hypothesis about how quick sort
operates on smaller sub arrays. Let's call
the length of the first part in the second
part of the partition [inaudible] K1 and
K2 respectively. Now, crucially, both k1
and k2 are strictly less than n. Both of
these two parts have lengths strictly less
than that of the given input array a.
That's because the pivot in particular is
excluded from both of those two parts. So,
their gonna have, at most n minus one
[inaudible]. That means that we can apply
the inductive hypothesis, which says that
the quicksort never makes a mistake on an
array that has size strictly less than n.
That implies that our two recursive calls
to quickstart, the one to the first part
and the one to the second part don't make
mistakes. They're guaranteed to sort those
sub arrays correctly by the inductive
hypothesis. And to be very precise, what
we're using to argue that the [inaudible]
are correct, are P of K1 and P of K2. Or P
is the assertion that [inaudible] is
always correct on a [inaudible]. K1 and
K2. And we know that both of these
statements are true because k1 and k2 are
less th, are both less than n and because
of the inductive hypothesis. So what's the
upshot? The upshot is, quicksort's gonna
be correct. And so the first recursive
call puts all of the elements that are
less than the pivot in the correct
relative order. Next comes the pivot,
which is bigger than all of that stuff in
the first part and less than all the stuff
in the second part, and then the second
recursive call correctly orders all of the
elements in the second part. So with those
three things pasted together, we have a
sorted version of the input array and
since this array was an arbitrary one, of
link N. That establishes the assertion P
of N and since n was arbitrary, that
establishes the inductive and completes
the proof of correctness of quick sort for
an arbitrary method of choosing the pivot
element. [sound]