- [Instructor] Hi, in the previous video
we introduced Quicksort
and in this video, we're going to implement Quicksort in C++
actually we're going to implement
a couple of different versions of Quicksort here.
And the first one that we're going to implement
we'll follow very closely the pseudocode
that was presented in the previous video.
So let's get started.
I'm gonna create a file,
I'm gonna call this Quicksort1
because we're gonna do another one later.
And I'm gonna borrow this snippet of code
that we've been using for printing vectors.
And that also includes a vector and iostream
which we're gonna need.
And if you'll recall from the pseudocode
that was presented in the previous video,
we have two functions that we're gonna look at.
One is the partition function
and the other is the recursive quicksort function.
I'm also gonna introduce something new today
which is called function overloading.
And I'll call that out when we get to the appropriate point
but it helps make our code in main a little cleaner.
And when we start comparing in our projects
a lot of different sorting algorithms, it may come in handy,
so that's why I'm gonna introduce that here today.
So let's copy this,
to get started, let's copy this template and code
and we're going to have a function that returns an int
that's going to be called partition,
and it's going to take a standard vector of comparables
and we'll call that V.
And then we also need the start and the end indices
since we're working with subdivisions of our vector.
So int start
and an end
and then the body of this function will go here.
Then we're also gonna have a void function
called quicksort,
that is gonna have exactly the same signature.
And I'm just gonna copy and paste that.
And let's create,
oh, I'm sorry didn't mean to paste that.
Let's create another,
and this is where the function overloading this coming in.
Void quicksort,
and this one is just gonna take
this bit here, the vector.
And this is okay in C++
to have two functions with the same name,
and the compiler understands
that they have two different signatures,
and we'll recognize when we write a function call
to quicksort and we only provide V
it will know to call this version of Quicksort.
And if we call quicksort with these three parameters
it will know to call this version of Quicksort.
And that's how simple a function overloading is.
So we have two functions in Quicksort,
but the compiler can tell the difference
based on their signatures.
And then finally we're gonna have main,
int main and I'm gonna have return zero.
Okay, so those are our placeholders,
those are our signatures for the functions.
So let's begin to flesh these out.
First, let's do quicksort, this one here.
Oops, again I didn't mean to paste that, sorry.
Okay, so what do we do?
It's a recursive function,
we have to have a base case here's the base case
if, and this is exactly what we had in our code
for mergesort, if end less than or equal to start,
that's if we have fewer than two elements, one or zero,
that's our base case and what do we do?
Same as mergesort, we just returned.
Okay, so this is the base case
of our recursion,
all right?
And then the recursive case.
Else, this is where we have two or more elements,
and I'll just put a note that this is the recursive case.
And we have int P equals partition V,
start and end.
And remember that partition is gonna return an int.
And then we make our two recursive calls
on either side of that partition.
So our vector is gonna be divided by P
and then we make a recursive call
on the portion of the vector that's to the right of P
and then another call to the portion
that's to the left of P.
And you'll recall that the values of the elements
to the left of P will be less than P
and the values to the right of P
will be greater than or equal to the value index by P.
Okay, so we have these two calls,
quicksort V, start
and this one's gonna run two P minus one.
Okay, that's the stuff to the left of P,
and then again, quicksort P,
and this is gonna run from P plus one to end,
and those are our two recursive calls.
And that's the complete function here.
Most of the work is gonna be done
in the partition function.
So let's do that now.
And if you recall,
the first thing we're gonna do is we're gonna set,
we're gonna get the value of the pivot,
comparable pivot
and we're gonna get the value at the end of our sub-sector.
So V, end,
and this is one way to get the pivot later on,
we'll take a look at another.
And that pivot in the book it's referred to as divider pivot
it's a far more common term,
if you look at other books or articles,
you'll see pivot more than you'll see divider.
And so this is the value
that we're going to use to partition.
So everything less than the pivot
is gonna go to one side
and everything that's greater than the pivot
is gonna go to the other side.
Okay, so we need to initialize this index to start.
And here we're following that pseudocode
that was presented in the previous video,
almost line by line
for int J equal start
to J, sorry, J less than or equal to the end plus J.
And then within the body of that loop,
the first thing we're gonna do
is we're gonna perform a comparison.
If V sub J is less than that pivot,
then we're gonna swap.
And what did we swap?
If you recall, again, from the previous video
we're gonna swap the values at V sub of i
and sub J, okay?
And then the swapping code should look very familiar
to you.
Comparable temp is gonna take the value of V sub J.
V sub J it's gonna take the value of V sub i
and V sub i is gonna take the value of temp.
There is our swap, and then we increment i.
Again as you recall, from the previous video
we increment i when we've made the swap.
And then we only have one other thing to do here.
And that is after this loop is finished,
we swap the values at the position V sub i at the end.
And that's our last step of the algorithm.
So I'm just gonna put a note to that effect here,
swap V sub i
and V, end,
and then this is gonna be pretty much the same,
comparable temp
equals V sub i this time.
V sub i gets the value at the end
and V end gets the value from the temp
and that completes our swap
and then the last thing we do is we return that index i,
return i.
And so that int that we return
becomes assigned to this variable P
and that's used as a divider
when we make our recursive calls.
So that is a complete implementation of quicksort.
Let's just flush out this other method here.
And all we're gonna do is since we're passing in
you'll see we're passing in the vector.
We wanna call quicksort
again with the vector V
and since we're only gonna use this
for the first call to quicksort for main,
we're going to run range over zero
to the last element of the vector,
which is indexed by V.size minus one.
And mostly what that's doing is
it's going to make our code in main a little prettier,
but also when we get to comparing many sorting algorithms
in our project, I think it's project four,
it will be convenient if all of the algorithms
have an entry point that looks the same,
where you just pass in a vector.
And so we have this little function
that just adds the extra parameters as needed.
So then we could call mergesort V, quicksort V,
bubblesort V and so on.
And you'll notice that some of the algorithms
take additional parameters like these here and some don't.
So this makes for a uniform presentation in main,
that's all it's doing.
Okay, so let's complete main.
This again should look familiar
based on some of the other sorting algorithms
and the main functions we've used to test them.
I'm just gonna run the algorithm through its paces,
so we need a vector,
standard vector of comparables,
oh, no, we're gonna make it a ints, sorry.
We'll call that V,
and let's give it some numbers, eight, five, zero,
four, three, nine, one,
seven, two, six.
Okay, that's all of the digits, zero to nine,
all jumbled up.
And then what are we gonna do?
Well, we're going to print vector P.
We're gonna call quicksort V,
and that's gonna call this one
and then this one is gonna call this
with the correct parameters.
And print vector P, again, that's it.
So if I haven't made any typos,
this looks good.
This should compile and run.
Okay, and let's run it
and it should print out the unsorted vector
and the sort of the vector
and that's exactly what we've got here.
Here's our unsorted doctor before the call to quicksort
and here is our sorted vector after the call to quicksort,
and that's exactly what we'd expect.
So now we've completed the first implementation.
Let's move on to a slightly different implementation
where we implement the median of three method
for choosing a pivot.
So now that we have that working,
let's continue and implement a version of Quicksort
using the median of three approach to choose the pivot.
You'll recall that we saw that in the previous video
and what I'm gonna do, I'm just gonna copy all this,
and make a few minor changes.
I'm gonna call this partition median three
and this will be quicksort median three
and it's going to call partition median three
and quicksort median three.
And what we're doing is guaranteeing
that we're going to call the correct version
of partition here, which we're gonna modify in a second.
And then quicksort media three.
And then in our main, we'll get to that a little later,
we'll call both of these
and make sure that they're both working.
So now what do we need to do?
We need to modify the partition function.
Wait, where did I go, I lost it?
There it is, okay.
We're gonna modify this partition function.
And if you recall, the median of three method
leaves the median value
of the starting element in the vector,
the middle element and the vector
and the ending element vector in the end position.
And we perform three comparisons on up to three swaps.
So the first thing we need to do
is calculate the middle of the vector or the sub vector
as the case maybe.
And we've seen this before in mergesort,
we have int middle
equals start plus end
divided by two.
And that's integer division as before
so if we have an on a little truncate.
And then we have three comparisons,
the first one, if the sub middle,
sorry, less than the sub start.
And then what do we do?
We swap middle and start.
And this should look let's just borrow this here
and make a few changes,
so we have comparable temp is gonna take V start.
V start is gonna take Vmiddle
and V middle is gonna take temp.
And that's our first case.
And we're gonna have two other cases
that look very much like this.
So let's just copy this now.
And our second is we're gonna compare end and start.
And if end is less than start
then we're gonna swap end and start.
And this swap is gonna be similar,
start, start, this one's gonna become end.
And this one and here,
and then, yeah, one more comparison,
and possibly one more swap
where we do middle and end?
Swap middle and end.
And then this becomes V middle, V end,
oh sorry, V middle gets V end
and V end gets temp.
And that's our median of three method here.
This parallels V pseudocode
that was presented in the previous video,
and it takes the beginning, middle and end elements
and chooses the median of three
and leaves that value in the end position.
And so now when we take this comparable pivot here
equal to V end, this V end is now the median
of the three and the other two
have been swapped into the appropriate positions as needed.
So that's the entirety of quicksort
using the median three approach.
And so now what we're gonna do
is we're gonna modify main a little bit.
I'm gonna call this a base vector
'cause we're gonna make copies of it
to make sure that the input to the two vectors we have
is the same.
And so we're gonna have quicksort median three
and here we're gonna have standard vector of ints,
sorry, the equal base vector.
We're just gonna make a copy of that, sorry, base vector.
And now we're gonna do the same thing here.
So we ensure that both the first Quicksort version
we implemented and the newer version using media three,
both get the exactly the same input.
So, if I haven't made any typos that should build,
okay, and it should run.
Let me do something here real quick.
Just putting in a blank line
to separate the outputs of these two tests here,
build and run.
And what we should see is two identical outputs.
Here's the unsorted input vector,
here's the sorted output vector,
here's the unsorted input vector
and the sorted output vector.
And now what we're gonna do is we're gonna set timers
on these algorithms and we're gonna supply the algorithms
with sorted and shuffled vectors to see how they perform.
Okay, so now what we're gonna do
is we're gonna set some timers on this
and we're gonna see
how Quicksort performs with and without
this median of three method for choosing the pivot.
So let me think,
what I'm gonna do,
actually, I'm gonna make a copy of this
and call it quicksort two and this'll be our timed version.
And we're gonna need to make some modifications
to the includes, so we're gonna need to include chrono
and that's for timing
and include random that's for shuffling, okay?
That print vector function stays the same.
All of these stay the same,
I guess we just
need to modify main, okay.
So in main, we're going to
want to be able to shuffle our vectors.
So we're going to need the standard random device,
call that rd, short for random device.
And then instead of this vector
we're gonna create a much bigger vector.
So standard vector int
we'll continue to call this a base vector,
but then we'll get rid of this.
And then we'll initialize it for int i equal zero,
i less than 10,000, say plus plus i.
And then what we're gonna do
is we're just gonna push that i on to the a vector.
So base vector
pushback i.
So that's gonna give us a vector of 10,000 elements
ranging from zero to 9,999.
And then we're gonna want to shuffle the vector.
So standard
shuffle base vector,
and we give begin
and the end
and the random device, rd.
And that's our syntax for a shuffling of vector.
And so now we should have a shuffled vector.
Let's do some tests and some timing.
First we're going to work with the shuffled vector.
So let's put a line in our output
to indicate that shuffled collector and
all right, and then vector into V equals base vector
and so we're not gonna want these print statements
'cause we don't wanna print out 10,000 elements,
that would be silly.
So what we're gonna do instead
is we're gonna set timers and let's see auto start time.
And I'll explain all this in a minute,
I think we've seen this before
but I will explain it in just a second,
equals let me think here, standard,
chrono, high resolution clock
and now.
And so what this is, oh, I got to booboo here,
how do I start time?
And so what this is doing is it's saying
auto is just a keyword that's saying a
C++ compiler I think you're smart enough to figure out
what type this is
and so it's gonna type start time for us.
And so here we have standard chrono
we're making reference to the chrono library
and this thing called the high resolution clock
and we're calling this a method called now,
and that's going to give a timestamp in microseconds, okay?
And then we're gonna run quicksort
and then we're gonna do exactly the same thing here,
we're just gonna copy this line,
make a call to exactly the same function,
except we're gonna call it end time,
and so we get the timestamp here
and the timestamp as soon as we're done,
that's in microseconds again.
And then we're gonna perform a little conversion
auto duration,
which is ultimately gonna be the start time
minus the end time but we have to do a little juggling here
equals a standard chrono
duration cast,
see how that filled it in automatically for us
standard chrono microseconds.
Okay, so we're saying we want this output all
in microseconds
and then we want end time, sorry,
end time minus start time and count.
And what count does, is it counts the microseconds
in that calculated interval.
And, well that's a long line,
but no, let's break it. I don't like long lines.
Okay, so that'll work.
And so what we're doing here is we're getting a timestamp
for the start, we're running quicksort,
we're getting the timestamp for the end time,
we're calculating the duration in microseconds
and then we will print the result.
And so that's standard cout,
excuse me quicksort
and we're gonna give the duration.
Now that's gonna be in microseconds
so it's gonna be a big number
and an endline.
And I'm not gonna fuss with formatting
it it'll be readable enough for us.
And then what we're gonna do
is we're gonna do exactly the same thing
for our quicksort median three.
And that's gonna be quicksort median three
and since we've already declared start time and end time
we don't need the autos here anymore
and duration we don't need anymore.
And so the code that we have here now,
let's just recap.
Let me just get rid of that.
Let's just recap real quick what we have here
is we're getting the random device
that we're gonna need for a shuffling,
we're creating a base vector of 10,000 elements.
We are shuffling that so that's gonna randomize
the order of all the elements in the vector
and then we're printing a little heading here
that we're working with a shuffled vector.
And then we are making a copy of that base vector,
we don't need this here, calling that V
and passing V to quicksort,
we're setting timers at the beginning of the end,
we're getting the duration
and we're gonna print out the duration,
put a blank line,
and we're going to then reassign based vector to V
we're gonna do the same thing
for the median of three algorithm and then print the result.
Now let's do that right now.
And again, if I don't have any typos
reload this
I need to add this, sorry, my bad.
Okay, so now we have to execute bubbles,
we can build quicksort2
and we'll run it and,
oops!
Okay, so here's shuffled vector and quicksort
and quicksort median of three
and almost exactly the same number of microseconds
with a shuffled vector as the input, okay?
Let's move this out here.
And now we're going to feed it as sorted vector
and see what the result is.
So let's go back.
And we are going to,
let's see what's the best way to do this,
that's base vector,
base vector clear,
clear is a method that just empties out a vector.
So whatever we had in that vector, that's gone now.
And now we're gonna initialize it
the same way we did before,
just taking the numbers from zero to 9,999
except this time we are not going to shuffle it.
And so we'll put a little heading here.
This is the sorted vector.
Okay, and then we're gonna take all this exact same stuff.
Okay, and just copy paste,
and we just need to make a few minor changes here,
we don't need these type specifiers
in the assignments
'cause we already know what those are.
And so now just to recap,
we've taken that base vector that shuffled vector,
and we've wiped out all of the values,
we've emptied into values.
And then we've created a new vector that's sorted.
If we just do this it's gonna give us a vector
that's in ascending order.
And so now we've printed out a little heading
that says sorted vector,
we assigned the base vector to V,
we set the timer, we were run quicksort,
we get the end time, we calculate the duration,
we put print the duration, and then the same thing
for the quicksort median three algorithm.
And again, if I've had no typos,
this should build.
Okay, that looks good, and now let's run it.
Now, look at the results here.
This is for our shuffled back there
and you can see the quicksort
and quicksort median of three have comparable performance,
so median three is slightly faster
and that's where the shuffled vector.
But now look at what happens with the sorted vector.
Quicksort performance deteriorates horribly.
This is 1, 293,000 microseconds
as compared to a little under 3000.
And here we have virtually the same performance
for the median of three version that we have above.
So you can see at least in this simple test,
that median of three vastly outperforms,
the version of quicksort where we just naively picked
from the end of the vector to choose our pivot.
So this clearly is a better method for choosing our pivot.
And I hope you found that coding session
and experiment instructive, okay?