The goal of this video is to provide more
details about the implementation of the
QuickSort algorithm and, in particular,
if you're ever going to drill down on the
key Partition subroutine, just let me
remind you what the job of the Partition
subroutine is in the context of sorting an
array. So recall that key idea in QuickSort
is to partition the input array around a
pivot element. So this has two steps.
First, you somehow choose a pivot element,
and in this video, we're not going to worry
about how you choose the pivot element.
For concreteness, you might just want to
think about you pick the first element
in the array to serve as
your pivot. So in this example array, the
first element happens to be 3, so we
can choose 3 as the pivot element.
Now, there's a key rearrangement step. So
you rearrange the array so that it has the
following properties. Any entries
that are to the left of the pivot element
should be less than the pivot element.
Whereas any entries, which are to the
right of the pivot element, should be
greater than the pivot element. So, for
example, in this, version of, the second
version of the array, we see to the left
of the 3 is the 2 and the 1.
They're in reverse order, but that's okay.
Both the 2 and the 1 are to the left
of the 3, and they're both less than 3.
And the five elements to the right
of the 3, they're jumbled up, but
they're all bigger than the pivot element.
So, this is a legitimate rearrangement
that satisfies the partitioning property.
And, again, recall that this definitely
makes partial progress toward having a
sorted array. The pivot element winds up
in its rightful position. It winds up
where it's supposed to be in the final
sorted array, to the right of everything
less than it, to the left of everything
bigger than it. Moreover, we've correctly
bucketed the other N-1 elements to
the left and to the right of the pivot
according to where they should wind up in
the final sorted array. So that's the job,
that the Partition subroutine is
responsible for. Now what's cool is we'll
be able to implement this Partition
subroutine in linear time. Even better,
we'll be able to implement it so that all
it does, really, is swaps in the array.
That is, it works in-place. It needs no
additional, essentially constant
additional memory, to rearrange the array
according to those properties. And then,
as we saw on the high-level description of
the QuickSort algorithm, what partitioning
does is, it enables a divide-and-conquer
approach. It reduces the problem size.
After you've partitioned the array around
the pivot, all you gotta do is recurse on
the left side, recurse on the right side,
and you're done. So, what I owe you is
this implementation. How do you actually
satisfy the partitioning property, stuff
to the left of the pivot is smaller than
it, stuff to the right of the pivot is
bigger than it, in linear time, and in-
place. Well, first, let's observe that, if
we didn't care about the in-place
requirement, if we were happy to just
allocate a second array and copy stuff
over, it would actually be pretty easy to
implement a Partition subroutine in
linear time. That is, using O(N) extra
memory, it's easy to partition around a
pivot element in O(N) time. And as
usual, you know, probably I should be more precise
and write theta of N, are used in cases that would
be the more accurate stronger statement,
but I'm going to be sloppy and I'm just
going to write the weaker but still
correct statement, using Big-Oh, okay? So
O(N) time using linear extra memory.
So how would you do this? Well let
me just sort of illustrate by example. I
think you'll get the idea. So let's go
back to our running example of an input
array. Well, if we're allowed to use
linear extra space, we can just
preallocate another array of length N.
Then we can just do a simple scan through
the input array, bucketing elements
according to whether they are bigger than
or less than the pivot. And, so for
example, we can fill in the additional
array both from the left and the right,
using elements that are less than or
bigger than the pivot respectively. So for
example we start with the 8, we know
that the 8 is bigger than the pivot,
so you put that at the end of the output
array. Then we get to the 2. The 2 is
less than the pivot, so that should go on
the left hand side of the output array.
When you get to the 5, it should go on the
right-hand side, and the 1 should go on
the left-hand side, and so on. When we
complete our scan through the input array,
there'll be one hole left, and that's
exactly where the pivot belongs, to the
right of everything less than it, to the
left of everything bigger than it. So,
what's really interesting, then, is to
have an implementation of Partition, which
is not merely linear time, but also uses
essentially no additional space. It
doesn't re-sort to this cop-out of
pre-allocating an extra array of
length N. So, let's turn to how that
works. First, starting at a high-level,
then filling in the details. So I'm
gonna describe the Partition subroutine
only for the case where the pivot is in
fact the first element. But really this is
without loss of generality. If, instead,
you want to use some pivot from the middle
of the array, you can just have a
preprocessing step that swaps the first
element of the array with the given pivot,
and then run the subroutine that I'm about
to describe, okay. So with constant time
preprocessing, the case of a general pivot
reduces to the case of when the pivot is
the first element. So here's the high-level
idea, and it's very cool. The idea is,
we're gonna be able to able to get
away with just a single linear scan of the
input array. So in any given moment in
this scan, there's just gonna be a single
for-Loop, we'll be keeping track of both
the part of the array we've looked at so
far, and the part that we haven't looked at
so far. So there's gonna be two groups,
what we've seen, what we haven't seen.
Then within the group we've seen, we're
gonna have definitely split further, according
to the elements that are less than the
pivot and those that are bigger than the
pivot. So we're gonna leave the pivot
element just hanging out in the first
element of the array until the very end of
the algorithm, when we correct its
position with a swap. And at any given
snapshot of this algorithm, we will have
some stuff that we've already looked at,
and some stuff that we haven't yet looked
at in our linear scan. Of course, we have
no idea what's up with the elements that
we haven't looked at yet, who knows
what they are, and whether they're bigger
or less than the pivot. But, we're gonna
implement the algorithm, so, among the
stuff that we've already seen, it will be
partitioned, in the sense that all
elements less than the pivot come first,
all elements bigger than the pivot come
last. And, as usual, we don't care about
the relative order, amongst elements less
than the pivot, or amongst elements bigger
than the pivot. So summarizing, we do a
single scan through the input array. And
the trick will be to maintain the
following invariant throughout the linear
scan. But basically, everything we have
looked at the input array is partitioned.
Everything less than the pivot comes
before everything bigger than the pivot.
And, we wanna maintain that invariant,
doing only constant work, and no
additional storage, with each step of our
linear scan.
So, here's what I'm gonna do next. I'm
gonna go through an example, and execute
the Partition subroutine on a concrete
array, the same input array we've been
using as an example, thus far. Now, maybe
it seems weird to give an example before
I've actually given you the algorithm,
before I've given you the code. But, doing
it this way, I think you'll see the gist
of what's going on in the example, and
then when I present the code, it'll be
very clear what's going on. Whereas, if I
presented the code first, it may seem a
little opaque when I first show you the
algorithm. So, let's start with an
example. Throughout the example, we wanna
keep in mind the high-level picture that
we discussed in the previous slide. The
goal is that, at any time in the Partition
subroutine, we've got the pivot hanging
out in the first entry. Then, we've got
stuff that we haven't looked at. So, of
course, who knows whether
those elements are bigger than or less
than the pivot? And then, for the stuff
we've looked at so far, everything less
than the pivot comes before everything
bigger than the pivot. This is the picture
we wanna retain, as we go through the
linear scan. As this high-level picture
would suggest, there is two boundaries
that we're gonna need to keep track of
throughout the algorithm. We're gonna need
to keep track of the boundary between what
we've looked at so far, and what we
haven't looked at yet. So, that's going to
be, we're going to use the index  "j" to keep
track of that boundary. And then, we also
need a second boundary, for amongst the
stuff that we've seen, where is the split
between those less than the pivot and
those bigger than the pivot. So, that's
gonna be "i". So, let's use our running
example array. >> So stuff is pretty
simple when we're starting out. We haven't
looked at anything. So all of this stuff
is unpartitioned. And "i" and  "j" both point
to the boundary between the pivot and all
the stuff that we haven't seen yet. Now to
get a running time reaches linear, we
want to make sure that at each step we
advance  "j", we look at one new element.
That way in a linear number of steps, we'll
have looked at everything, and hopefully
we'll be done, and we'll have a partitioned
array. So, in the next step, we're going to
advance  "j". So the region of the array
which is, which we haven't looked at,
which is unpartitioned, is one smaller
than before. We've now looked at the
8, the first element after the pivot.
Now the 8 itself is indeed a
partitioned array. Everything less than
the pivot comes before, everything after
the pivot turns out there's nothing less
than the pivot. So vacuously this is
indeed partitioned. So  "j" records
delineates the boundary between what we've
looked at and what we haven't looked at, "i"
delineates amongst the stuff we've looked
at, where is the boundary between what's
bigger than and what's less than the
pivot. So the 8 is bigger than the pivot,
so "i" should be right here. Okay, because we
want "i" to be just to the left of all the
stuff bigger than the pivot. Now, what's
gonna happen in the next iteration? This
is where things get interesting. Suppose
we advance  "j" one further. Now the part of
the array that we've seen is an 8
followed by a 2. Now an 8 and a 2
is not a partitioned subarray. Remember
what it means to be a partitioned
subarray? All the stuff less
than the pivot, all the stuff less than
3, should come before everything
bigger than 3. So (8, 2) obviously
fails that property. 2 is less than the
pivot, but it comes after the 8, which
is bigger than the pivot. So, to correct
this, we're going to need to do a swap.
We're going to swap the 2 and the 8.
That gives us the following version of the
original array. So now the stuff that we
have not yet looked at is one smaller than
before. We've advanced  "j". So all other
stuff is unpartitioned. Who knows what's
going on with that stuff?  "j" is one further
entry to the right than it was before, and
at least after we have done this swap, we
do indeed have a partitioned array. So
post-swap, the 2 and the 8, are
indeed partitioned. Now remember, "I"
delineates the boundary between amongst
what we've seen so far, the stuff less
than the pivot, less than 3 in this
case, and that bigger than 3, so "I" is
going to be wedged in between the 2 and
the 8. In the next iteration, our life
is pretty easy. So, in this case, in
advancing  "j", we uncover an element which
is bigger than the pivot. So, this is what
happened in the first iteration, when we
uncovered the 8. It's different than
what happened in the last iteration when
we uncovered the 2. And so, this case,
this third iteration is gonna be more
similar to the first iteration than the
second iteration. In particular, we won't
need to swap. We won't need to advance "i".
We just advance  "j", and we're done. So,
let's see why that's true. So, we've
advanced  "j". We've done one more iteration.
So, now the stuff we haven't seen yet is
only the last four elements. So, who knows
what's up with, the stuff we haven't seen
yet? But if you look at the stuff we have
seen, the 2, the 8, and the 5,
this is, in fact, partitioned, right? All
the numbers that are bigger than 3
succeed, come after, all the numbers
smaller than three. So the "j",
the boundary between what we've seen and
what we haven't is between the 5 and
the 1; and the "i", the boundary between
the stuff less than the pivot and bigger
than the pivot is between the 2 and the
8, just like it was before. Adding a
5 to the end didn't change anything. So
let's wrap up this example in the next
slide. So first, let's just remember where
we left off from the previous slide. So
I'm just gonna redraw that same step after
three iterations of the algorithm. And
notice, in the next generation, we're going
to, again, have to make some modifications
to the array, if we want preserve our
variant. The reason is that when we
advance  "j", when we scan this 1, now
again we're scanning in a new element
which is less than the pivot, and what
that means is that, the partitioned
region, or the region that we've looked at
so far, will not be partitioned. We'll
have 2851. Remember we need everything
less than 3 to precede everything
bigger than 3, and this 1
at end is not going to cut it. So we're
going to have to make a swap. Now what are
we going to swap? We're going to swap the
1 and the 8. So, why do we swap the
1 and the 8? Well, clearly, we have
to swap the 1 with something. And, what
makes sense? What makes sense is the
left-most array entry, which is currently
bigger than the pivot. And, that's exactly
the 8. Okay, that's the first,
left-most entry bigger than 3, so if
we swap the 1 with it, then the 1 will
become the right-most entry smaller than
3. So after the swap, we're gonna have
the following array. The stuff we haven't
seen is the 4, the 7, and the 6.
So the  "j" will be between the 8 and the
4. The stuff we have seen is the 2,
1, 5, and 8. And notice, that
this is indeed partitioned. All the
elements, which are less than 3, the
2 and the 1, precede all of the
entries, which are bigger than 3, the
5 and the 8. "i", remember, is
supposed to split, be the boundary
between those less than 3 and those
bigger than 3. So, that's gonna lie
between the 1 and the 5. That is one
further to the right than it was in the
previous iteration. Okay, so the, because
the rest of the unseen elements, the 4,
the 7, and the 6, are all bigger
than the pivot, the last three iterations
are easy. No further swaps are necessary.
No increments to "i" are necessary.  "j" is just
going to get incremented until we fall off
the array. And then, fast forwarding, the
Partition subroutine, or this main linear
scan, will terminate with the following
situation. So at this point, all of the
elements have been seen, all the elements
are partitioned.  "j" in effect has fallen
off the end of the array, and "i", the boundary
between those less than and bigger than
the pivot, still lies between the 1 and
the 5. Now, we're not quite done,
because the pivot element 3 is not in
the correct place. Remember, what we're
aiming for is an array where everything
less than the pivot is to the left of it,
and everything bigger than the pivot is to
the right. But right now, the pivot still
is hanging out in the first element. So,
we just have to swap that into the correct
place. Where's the correct place? Well,
it's going to be the right-most element,
which is smaller than the pivot. So, in
this case, the 1. So the subroutine will
terminate with the following array,
12358476. And, indeed, as desired,
everything to the left of the pivot
is less than the pivot, and everything to
the right of the pivot is bigger than the
pivot. The 1 and 2 happen to be in
sorted order, but that was just sorta an
accident. And the 4, 5, 6 and
7 and 8, you'll notice, are jumbled
up. They're not in sorted order. So
hopefully from this example you have a
gist of how the Partition subroutine is
going to work in general. But, just to
make sure the details are clear, let me
now describe the pseudocode for the
Partition subroutine. So the way I'm going
to denote it is, there's going to be an
input array A. But rather than being told
some explicit link, what's going to be
passed to the subroutine are two array
indices. The leftmost index, which
delineates this part of the separator
you're supposed to work on, and the
rightmost index. The reason I'm writing it
this way is because Partition is going to
be called recursively from within a QuickSort
algorithm. So any point in QuickSort,
we're going to be recursing on some
subset, contiguous subset of the original
input array. "l(el)" and "r" meant to denote
what the left boundary and the right
boundary of that subarray are. So, let's
not lose sight of the high-level picture
of the invariant that the algorithm is
meant to maintain. So, as we discussed,
we're assuming the pivot element is the
first element, although that's really
without loss of generality. At any given
time, there's gonna be stuff we haven't
seen yet. Who knows what's up with that?
And, amongst the stuff we've seen, we're
gonna maintain the invariant that all the
stuff less than the pivot comes before all
the stuff bigger than the pivot. And  "j" and
I denote the boundaries, between the seen
and the unseen, and between the small
elements and the large elements,
respectively. So back to the pseudocode,
we initialize the pivot to be the first
entry in the array. And again remember, l
denotes the leftmost index that we're
responsible for looking at. Initial value
of "i", should be just to the right of the
pivot so that's gonna be el+1.
That's also the initial value of  "j", which
will be assigned in the main for-Loop. So this
for-Loop with "j", taking on all values from
el+1 to the rightmost index "r",
denotes the linear scan through the input array. And,
what we saw in the example is that there
were two cases, depending on, for the
newly seen element, whether it's bigger
than the pivot, or less than the pivot.
The easy case is when it's bigger than the
pivot. Then we essentially don't have to
do anything. Remember, we didn't do any
swaps, we didn't change "i", the boundary
didn't change. It was when the new element
was less than the pivot that we had to do
some work. So, we're gonna check that, is
the newly seen element, A[j], less than "p".
And if it's not, we actually don't have to do
anything. So let me just put as a
comment. If the new element is bigger than
the pivot, we do nothing. Of course at the
end of the for-Loop, the value of  "j" will
get in command so that's the only thing
that changes from iteration to iteration,
when we're sucking up new elements that
happen to be bigger than "p". So what do we
do in the example, when we suck up our new
element less than p? Well we have to do
two things. So, in the event that the
newly seen element is less than "p", I'll
circle that here in pink. We need to do a
rearrangement, so we, again, have a
partitioned, sub-array amongst those
elements we've seen so far. And, the best
way to do that is to swap this new element
with the left-most element that's bigger
than the pivot. And because we have an
index "i", which is keeping track of the
boundary between the elements less than
the pivot and bigger than the pivot, we can
immediately access the leftmost element
bigger than the pivot.
That's just the "i"th
entry in the array. Now I am
doing something a little sneaky here,
I should be honest about. Which is there is
the case where you haven't yet seen any
elements bigger than the pivot, and then
you don't actually have a leftmost
element bigger than the pivot to swap
with. Turns out this code still works,
I'll let you verify that, but it does do
some redundant swaps. Really, you don't
need to do any swaps until you first see
some elements bigger than the pivot, and
then see some elements less than the
pivot. So, you can imagine a different
limitation of this, where you
actually keep track of whether or not
that's happened to avoid the redundant
swaps. I'm just gonna give you the
simple pseudocode. And again, for
intuition, you wanna think about the case
just like, in the picture here in blue,
where we've already seen some elements
that are bigger than the pivot, and the
next newly seen element is less than the
pivot. That's really sort of the key case
here. Now the other thing we have to do
after one of these swaps is, now the
boundary, between where the array elements
less than the pivot and
those bigger than the pivot, has moved.
It's moved one to the right, so
we have to increment "i". So, that's the
main linear scan. Once this concludes,  "j"
will have fallen off the end of the array.
And, everything that we've seen the final
elements, except for the pivot, will be
arranged so that those less than "p" are
first, those bigger than "p" will be last.
The final thing we have to do is just swap
the pivot into its rightful position. And,
recall for that, we just swap it with the
right-most element less than it. So, that
is it. That is the Partition subroutine.
There's a number of variants of partition.
This is certainly not the unique
implementation. If you look on the web, or
if you look in certain textbooks, you'll
find some other implementations as well as
discussion of the various merits. But, I
hope this gives you, I mean, this is a
canonical implementation, and I hope it
gives you a clear picture of how you
rearrange the array using in-place swaps
to get the desired property, that all the
stuff before the pivot comes first, all
the stuff after the pivot comes last.
Let me just add a few details about why
this pseudocode I just gave you does,
indeed, have the properties required. The
running time is O(N), really theta of N,
but again, I'll be sloppy and write
O(N). Where N is the number of array
elements that we have to look at. So, N is
r-el+1, which is the length of
the sub-array that this Partition
subroutine is invoked upon. And why is
this true? Well if you just go inspect the
pseudocode, you can just count it up
naively and you'll find that this is true.
We just do a linear scan through the array
and all we do is basically a comparison
and possibly a swap and an increment for
each array entry that we see. Also, if you
inspect the code, it is evident that it
works in-place. We do not allocate some
second copy of an array to populate, like
we did in the naive Partition
subroutine. All we do is repeated swaps.
Correctness of the subroutine follows by
induction, so in particular the best way
to argue it is by invariant. So I'll state
the invariant here, but mostly leave it
for you to check that indeed, every
iteration of the for-Loop maintains this
invariant. So first of all, all of the
stuff to the right of the pivot element,
to the right of the leftmost entry and up
to the index "i", is indeed less than the
pivot element, as suggested by the
picture. And also suggested by the
picture, everything beginning with the "i"th
entry, leading just up before the "j"th entry,
is bigger than the pivot. And I'll
leave it as a good exercise for you to
check that this holds by induction.
The invariant holds initially,
when both "i" and  "j" are equal to el+1,
because both of these sets are vacuous, okay?
So, there are no such elements, so they're
trivially satisfied these properties. And
then, every time we advance  "j", well, in
one case it's very easy, where the new
element is bigger than the pivot. It's
clear that, if the invariant held before,
it also holds at, at the next iteration.
And then, if you think about it carefully,
this swap in this increment of "i" that we
do, in the case where the new element is
less than the pivot. After the swap, once
the fold is complete, again if this
invariant was true at the beginning of it,
it's also true at the end. So what good is
that? Well, by this claim, at the
conclusion of the linear scan at which
point "j" has fallen off the end of the
array, the array must look like this. At
the end of the for-Loop, the question
mark part of the array has vanished, so
everything other than the pivot has been
organized so that all this stuff less than
the pivot comes before everything after
the pivot, and that means once you do the
final swap, once you swap the pivot
element from its first and left most
entry, with the right most entry less than
the pivot, you're done. Okay? You've got
the desired property that everything to
the left of the pivot is less than, and
everything to the right of the pivot is
bigger than. So now that given a pivot
element we understand how to very quickly
rearrange the array so that it's
partitioned around that pivot element,
let's move on to understanding how that
pivot element should be chosen and how,
given suitable choices of that pivot
element, we can implement the QuickSort
algorithm, to run very quickly, in
particular, on average in O(N) log time.