- [Instructor] Okay.
So in the previous video,
we gave a brief introduction to selection sort,
and we showed some pseudo-code
and walked through how selection sort works.
In this video we're going to code it up
in C plus plus like we did with bubble sort.
So let's start
and we'll create a new file again I'm gonna put everything
in one file, no headers, no fuss, no Moss.
And we'll call this selection sort.
Okay.
And we're gonna need a couple of things,
We're gonna need vector.
And we're gonna need iostream.
And then I'm gonna go to the code
that we had from the last time.
And I'm gonna borrow this code here
that we use this function for printing the vector.
We're just gonna borrow that copy paste.
Okay.
And then we're going to create a function
that implements selection sort.
And that's gonna take us in your,
vector
And we'll make that comparable
As before.
Let's just copy this template code here too.
And so now we need to complete the body of the function.
Now let's recall what happens in selection sort.
In selection sort we take a vector
and it's divided into two parts
in the first iteration.
One part is empty and the other part is the entire vector.
And we find the minimum value.
And then we swap the minimum value that we find
in the unsorted part
with the left most element in the vector
of the element with the smallest index.
And then we just continue to iterate.
So we're going to need a for loop
and we'll call the swap index,
and swap index.
Less than the size of the vector,
and Increment swap Index.
And that's our outer loop.
Then inside,
we're going to have integer,
variable mean index.
Use the index of the minimum
and we're gonna set that to swap index to start.
Then we're gonna have our inner loop
for I equal swap index plus one
because we start the iteration of our inner loop
from the first unsorted element in our vector.
And I less than
and increment.
This is the loop where we're finding the index
of the minimum value
in the unsorted portion of our effector.
So if the sub pop user by is less
than the current, the index,
then we found a smaller value.
And so we'll update mean index
with high,
simple as that.
So when we encounter a smaller value,
we update that mean index value.
Having completed that inner loop.
Now we know the smallest element
in the unsorted portion of the vector.
And so we're going to swap it with the appropriate element
but to complete the outer loop.
So we'll swap comparable,
and call it temp.
And this should look similar to what we did in bubble sort.
That's the element in the vector.
That's the smallest minimum value in the unsorted portion.
And then,
in index,
we'll take,
this one we swap it.
That's the left most on the sorted.
And then we do V swap index will take time.
And that my friends is our selection sort.
I'm gonna put in a little extra code here
that is not strictly necessary for selection sort,
but will help us keep track of what's going on
and allow us to compare the result
we get with selection sort
with what we get from bubble sort.
So I'm gonna put In two additional variables here
and again these are not necessary
for the implementation of selection sort.
Int and I'm gonna call this non comparisons.
which is gonna track the number of comparisons that we make
and Int num swaps
we'll set that also equal to zero
So we can count the number of comparisons
in the number of swaps
that we make when we go through this algorithm.
And so where do we make comparisons?
We're gonna make comparisons in this inner loop here
where we're searching for the minimum value
in the unsorted portion of our vector.
And so every time we iterate
through this part, this inner loop
we're going to increase num comparisons,
we're keeping count
so every iteration of that inner loop
is gonna be another comparison.
And then when we get down here,
we've made a swap so we're gonna count numb swaps.
Okay.
And then at the very end,
let's put in a little code to print out what we've done.
So under see out comparisons
and then numb comparisons,
and then a standard in line.
And then one more line,
to print out the number of swaps.
And now let's write a little main function here
Int main,
and what we're gonna do here is we're gonna create a vector
so we can test our selection sort algorithm.
And so I'll need a vector
and we'll make it a vector of ints cause that's easy.
We'll call it V and we'll initialize it just the way we did
in the last one using these curly braces.
So four, nine, seven, three, eight, five zero, one, two, six
and that's all our values from zero to nine,
which should be fine.
And we'll print that vector
and then we'll do a selection sort on it.
And you know what?
I forgot something.
I'm gonna do one more thing here.
Let me do numb swaps.
I'm gonna do vector.
Just like we did with bubble sorts.
So we can see at each iteration of the outer loop
what the vector looks like as we're sorting it.
Okay.
So now we have the house
This is the actual code
that's implementing selection sort minus this line here.
The rest is for our own purposes here in demonstration,
And then we haven't mean where we create a vector
we're gonna print the vector,
we're gonna sort the vector
and every time we iterate on that outer loop
we're gonna get a print out of the vector.
So let's give it a try.
Okay. So
this looks about right let's just walk through this
and make sure that this
is in accordance with our expectations.
So we start with this input factor,
which agrees with this year,
and then we search the entire thing
and we find the minimum value and we swap that with four.
So now we find that zero and four are swapped
see here's zero and four and zero four.
And then we go through the next iteration
and we only search this part of the vector.
And we find the smallest value is one
and we swap that with nine
and you see we're swapping nine and one here.
And so we get this vector and then we search this part
of the vector and we find the minimum value
which is two that gets swapped with seven.
And you can see swap seven
and two are being swapped here
and we get this factor.
And one more time,
then we search this part
and we find three
and three is already in the correct position.
So we swap three with three
and we wind up in the same place.
And so nothing happened in that iteration.
And then we search
this part here, sorry,
and we find four
we swap four with eight.
So this looks like it's doing exactly
what we expect it to do.
And our little bookkeeping is telling us
that we performed 45 comparisons and 10 swaps.
And if you recall,
you can see here
we have 10 elements in our vector.
We've performed exactly 10 swaps.
And that is exactly what we expect.
And so now, just for the sake of comparison
we compared a selection sort, a bubble sort
in the earlier video,
let's just copy and paste some code
from our bubble sort
from the last coding session.
And we already have that.
We already have included in that the code that keeps track
of the number of comparisons
let's also put in code
that keeps track of the number of swaps
and num swaps
let's call that just probable search
cause we don't have three anymore.
Okay.
And where do we swap?
We swap here.
So here is where we will increment num swaps.
And then let's just borrow this code here
cause that's gonna be identical in both.
And this will print out the number of comparisons
in the number of swaps that we've made for bubble sort.
And so let's just copy all this,
and we don't need this.
We're gonna do bubble sort
and let's just put a blank line between them.
Okay. So there we go.
So now let's run this
and compare,
Oh, dear.
we have a problem.
I forgot to initialize them swaps.
See that bad, bad, bad.
Do it again.
Sorry. Okay.
So here we are.
Here's our output.
What we have in the beginning, this is our selection sort
notice that it has to go through 10 times
if it has 10 elements, but it only makes 10 swaps.
Because bubble sort knows how to bail out early.
If it's not making any more swaps, we only do one, two
three, four, five, six, seven iterations
before it's finished.
It performs 42 comparisons, but it performs 29 swaps
which is almost three times the number of swaps
that selection sort makes.
And so let's just go back to the code real quick.
So we can end on this.
This is our implementation of selection sort
with a little extra bookkeeping.
And I hope that makes it clear to you
how selection sort works.