- [Instructor] Hi.
I think in one of the earlier videos,
I mentioned that
we would do a stable version of Quicksort.
And so let's do that.
I'm gonna create a new file
called quicksortStable.
Okay,
and I'm going to include
vector
and IO stream.
Okay, and let's borrow that snippet
for printVector.
That's just for printing a vector.
And now we're going to need
a function for quicksortStable
void
quicksortStable.
And that's gonna take a standard vector
of comparables,
and we'll call that V.
And we should also borrow this template and code here,
just so you know,
SeaLion collapses that,
and if you click on it,
it'll expand to show the full template and code.
All right.
So, also we need main.
Okay.
So let's do a stable version of Quicksort.
And as I mentioned,
in order to make Quicksort stable,
it comes at a price.
What is the price?
The price is space.
So we're gonna need to use more space
for this version of Quicksort
than we do with the other version
of Quicksort that I've already demonstrated.
Now this is going to work very similarly
to the Quicksort we've seen before
but we're going to have to make some changes,
and you'll see what we're going to do
is we're going to use vectors
to hold our intermediate results,
and that's where the extra space is gonna come from.
So we'll have a base case for the recursion.
Okay, and that's going to be if
the vector size
is less than two.
Then we have a single element,
and we just return.
Okay, so there's our base case.
Now we're going to set up our pivot
or what's called the divider
in the book,
comparable pivot.
And in this case, let's pick from the left-hand side.
So we'll take v sub zero,
and now we're going to need some vectors
to hold our intermediate results.
So standard
vector
of comparables,
and we'll call them smaller,
for the values that are smaller than the pivot,
equal
and larger.
Okay.
So that's where our additional space requirement
is gonna come from.
I'm gonna declare an integer i,
that we're going to use,
and it's okay to declare this here.
And then we have a loop for
i equals zero,
i less than the size of the input vector,
++i,
and here's the core of this thing.
If
v sub i
is less than the pivot,
then we push that onto the vector called "smaller."
Else,
if
v sub i
is greater
than the value of the pivot,
then it's going to go,
I think you know what I'm gonna do here.
Larger.
Push back
v sub i.
So we're putting that onto the larger vector,
else, and you know what comes here, equal.
That's our equal vector pushback
v sub i.
So you see what we've done.
We're just going to take our elements
from our vector in turn,
and push them into the smaller vector
if there are less than the pivot,
the larger vector,
if they're greater than the pivot
or the equal vector
if they're equal to the pivot.
Okay,
and now what do we need to do?
We need to call Quicksort recursively.
Okay, so we have these vectors.
We wanna work with a smaller vector,
and we want to work with the larger vector,
because what's in the smaller vector
still needs to be sorted,
and what's in the larger vector
still needs to be sorted,
or I should say the vector named "larger."
All right, so we're just gonna call
recursively quicksortStable, smaller,
I'm to pass that smaller vector
to quicksortStable,
and quicksortStable,
we're gonna pass that vector called "larger."
And now when we're done,
when those recursive calls return,
then we're ready to copy everything back
to the original vector.
So for,
i equals zero,
i less than smaller size,
sorry.
Okay,
++i,
then we're going to copy values
from the vector named "smaller" into v.
So v i is our index,
smaller i.
And now we need to
work with,
I'm going to show you another trick here.
This is for...
Semicolon
i,
less than smaller size,
plus equal size,
++i.
Now, what have I just done here?
You notice I've omitted the initialization of i,
and I can do that, that's fine.
This is perfectly legitimate C++.
But what it's doing,
and this is why I declared i up here,
for i equals zero,
We're gonna increment i
up to the size of this smaller index,
and then we're just gonna continue.
So the value of i
is going to roll over
into this loop,
and we're going to continue incrementing
through this value here,
the smaller size plus the equal size.
And then let me just show you
so this will make a little more sense
before I complete the bodies of those four loops.
For, we're going to do it again,
semicolon,
i,
less than v size,
that's the size of the whole vector.
I could say smaller plus equal plus larger,
but it's all going to be the same thing,
++i.
And so what we're doing
is we're incrementing i up until this point,
then we're going to continue to increment i
as we fill in using values from the equal vector,
and then we're going to continue using,
filling in the vector v
using values from that larger vector.
And so let's flesh out those bodies here,
v sub i
gets the value of equal
i,
minus the smaller size,
'cause of course,
each vector is to start at zero index.
And then finally, v sub i here,
gets from the vector called "larger,"
but here the index is i,
sorry, i
minus smaller size,
minus equal size,
again because
the larger vector is going to start at index zero.
And that's it.
That is our stable Quicksort algorithm.
So that's the base case for the conversion.
I should put this up here.
This is the recursive case.
Okay. And that's it.
So let's test it.
We need to flesh out main here now.
So we need a vector to test,
and we'll make it a vector of int,
as we've been doing so far to test,
and we'll plug in
8,
5,
0,
4,
3,
9,
1,
7,
2,
6,
and that's all of our digits, zero through nine.
And then we're going to print vector v,
and then we're going to quicksortStable v,
and then print vector v.
So now if we run this,
we will print out this unsorted vector
we'll run quicksortStable,
it'll make all the necessary recursive calls
as it divvies things up
into those three intermediate vectors.
And then we'll wind up with a sorted vector,
and we'll print that out.
So let's do that.
Let me make sure this is okay,
we'll call this Quicksort, that's good.
So let's run.
Hopefully there are no typos,
and that's it.
So you see what we've done here.
Here's our input vector,
here's our sorted output vector,
but by putting everything
into these separate vectors with pushback,
we preserve the order in which they arrived,
and so it's going to preserve the order
as we copy them back out to v
in this portion of the code.
And so this algorithm is gonna be stable,
which is what we wanted.
So that's an implementation
of Quicksort in a stable version.
That's all.