Hey everyone.
Welcome back.
So in this video.
Let us now continue our discussion.
And now let's implement the selection sort algorithm.
Now in the last video we discussed what exactly selection sort is the basic idea behind the scheme.
As well as we saw the example via visualization and via our own dry run.
So for selection sort.
Let us take the same array.
Let us say we are given elements which are 1225, 1134, 90 and 22.
Now what happens when you are going from discussion or intuition to implementation?
We have to.
Now think in terms of indexes in terms of size and everything.
Right.
So during the intuition and understanding an algorithm we were actually able to just see that okay what
are we doing.
Right.
We understood that yes we have to find the minimum then swap the place, and we were not that much hung
up upon.
What is the size of the array?
What exactly are we working on?
But any algorithm which we have to now implement.
Okay.
And the same will be true going forward as well for other solution for any problem as well.
When we get into implementation, we have to make sure that we are focusing on each and every small
detail as well.
That is especially very important for the starting questions, which you do.
So with that in mind, if we see the very first thing which I think we should write is the indexes of
my array, because I will be now accessing each and every element with the index only.
Next thing is we should also have the size, which is the length of my array, which in this case is
of course six.
Great.
Now let us see what we used to do when we used to do the selection sort.
Right.
So we used to start Okay.
Let's say we are starting from zero.
Here we used to take a minimum, and we used to say that current one is the minimum.
If you even remember in the visualization which I showed to you in the last video, it was maintaining
that the red one, the minimum one initially is the from where we are starting.
So minimum will be zero as well and we go till end.
So n in this case will be five not six.
Because now we are talking in terms of n indexes.
And then we used to find that where is the minimum the actual minimum element.
Right.
So let us call that overall min index okay.
Or rather we can take it min only after working out everything we used to get the right min index.
So I am talking in terms of indexes.
You can do it in terms of values as well.
But normally you will be requiring index for sure because that is where we will make the change.
Now we find the actual minimum is present on two.
Okay.
So let us just try to code this once everyone.
So let us go to VS code what we have to code.
We will be coding just the first pass or the first iteration.
The first round.
We will maintain that zero is my minimum.
Initially we will start from zero, go all the way till end, and will make sure that we are able to
find the actual minimum index.
Okay, great.
So let us define a function selection sort where I will be getting an array right.
So where I will be getting an array.
Now let us copy this part so we can just use the same part everyone.
The array which we took is 1225 1134 1922.
So the same one which we have on screen instead of bourbon, it will be selection sort.
Great.
The very first thing again n is equal to length of array.
Now in N, we have the length of array which will be six.
Here let us write the first pass.
In first pass I am saying my min index is initially zero, right everyone?
So I am assuming right that 12 is the minimum, something which we saw on the visualization as well.
So if I just show you that from start, let us see that.
See 12 is said to be minimum.
And now we keep on comparing as and when I find another element which is minimum than my 12, I update
my minimum.
So you will see that red gets changed, right?
So that the red one is the minimum index or the minimum element.
And this is getting changed here.
See it will become 11.
Now we will go.
And finally we will swap both both of them okay.
So pay attention everyone.
Minimum index is this I have to now go for J in range.
We have to now start from one right.
We have to start from one.
The reason being we are taking this already a minimum, so we should not compare this with itself.
So it will be 12N it will run till n minus one which is five.
Okay, so that part seems to be fine.
We have to run till five only great if array of j.
Okay, so all the elements which I am visiting if it is less than array which I have on my minimum index,
then I think we should do the same thing which the visualization did.
That is to update our minimum index.
So pay attention everyone.
Let us see what happened.
It is 12 here.
I went to 25.
Nothing is going to happen if I go to 11.
This time the element is less than current minimum.
So set element as the new minimum.
Okay, so I have the minimum index.
Now once I complete this particular loop what I have to do I have to swap the minimum index and the
ith from where I am starting.
So this currently is zero.
I am on zeroth position and array of min index, right?
All I'm saying is I am on zero min index seems to be two.
Let us swap them.
So array of min index and array of zero.
And now what should happen if we have written this perfectly?
Fine.
The minimum should reach to the first position.
One thing more.
Everyone.
Please make sure that you are aware on the intermediate steps.
Many times it happens in quotients which you will be asked in many tier one companies like Google,
Amazon, Microsoft, Goldman Sachs is that interviewer is interested in knowing your thought process.
So if you are able to solve for a single step and then take him through the journey where you are finally
reaching to the solution, the same is very helpful.
Rather than remembering the code or any particular, I would say hack to solve the question.
Let us run this now.
One second.
one's okay.
We have not returned anything, so let us return the array as well.
And now let us run this.
And I am able to get 11 to the starting gate.
Now again what I have to do.
Just like in Bubblesort, let us add a loop outside.
So for I in range I have to go till n, or rather I would say n minus one.
Okay, because in the last I will be running for these elements.
These elements and the last one will of course obviously be in the end.
Then this time minimum index see after first pass here.
If you see this after first pass is complete this is sorted now okay.
So we move forward.
11 is now in the sorted position.
Now my red one will become 25, in the next it will become 12.
So that means instead of zero it should be I.
Okay right.
Similarly I will not be starting from one all the time.
This time I will be starting from two.
For two, I will be starting on three.
So what does that mean?
Effectively is that I am sitting on.
I let me change the color I am sitting on I and the next one is I plus one from where I have to start.
So I plus one till end.
I have to go.
When we were on zero it was from one to n when we were on one.
It will be from two to N on two it will be on three to N right.
So this is next time.
This will be the array which I have to see for minimum.
Great.
Let us clear all this and make it I plus one.
Now if array of j less than array of min index then we will be swapping.
We will be changing the min index.
But here as well.
Again I have to do the final change on I.
Okay great.
So yeah I think that should do all the work.
Everyone we have just transformed what all we understood into a very good, understandable code.
Let us run this now and we are able to get everything sorted.
Okay, so in the right you will see the output.
They are sorted 11 1222.
Yeah.
I can take another example.
Let us just comment this first an empty list example.
We are able to get an empty list.
Seems to work fine.
(543) 211-2345 seems to be working fine.
Absolutely fine.
A single element I am getting a single element.
So these are few boundary or edge cases which again you have to check.
Okay, so great everyone.
I hope the overall implementation is clear on how exactly we do that.
Do this particular thing.
Let me do one more thing.
Let me just copy this overall link so that you can also understand by visualizing.
Right.
So when you try to revise it you have this visualization link in your solution file only.
Okay.
So cool everyone please try to do it if you have not.
If you are not able to do the same in the coding exercise, and we are going to meet in the next video.