Hello everyone and welcome back.
So in this video let us now continue our discussion on sorting.
And now let's learn about the second algorithm in sorting which is the selection sort.
Just like bubble sort, selection sort is another algorithm which helps us to sort our given array.
Now let us try to understand that similarly the way we did about bubble sort, let's say this time as
well, we will be given a list of integers or elements, right.
So 12.
Then we have 25, 11, 34, 90 and 22.
Great.
Now let us discuss about the philosophy of selection sort.
As the name suggests, the very important thing is select.
In selection sort, what I do is I try to select each and every element one by one.
Okay.
So I will be making sure that first light is right.
Okay.
What is the output?
Okay.
So let's see the final output.
11 1222
2534 and 90.
So in selection sort what I do is I compare that okay 11 is here.
Okay.
Why is 11 here.
Because it is the minimum element right.
It is the minimum element.
So I will be going to each and every element and asking if it's the minimum.
Okay.
So in the round one this time in the past one, I will try to find which is the minimum element in all
of my given array.
We can see that it is 11.
We should try that.
11 should come to its right position.
But before I do that, I think I will have to make sure that I don't lose this.
12 so what we do is we swap them.
Okay, so let me write the overall idea in each pass.
We see the array.
And select the minimum.
Now once you have the minimum we just we swap that.
To the or to its right position.
Okay.
So in the round one or in the past one what is going to happen.
Everyone we will see that 11 is there and 12 is there.
Rest all elements.
They will not be affected.
But again you will think that the overall list or array is not sorted.
And you're absolutely right.
But have we achieved something again this time?
I believe yes, we have achieved something.
Let me just write them in different colour.
So let us have green here and let us have 12 with this.
I think what we have achieved here is that we got one element at the right position.
Okay.
So just like in bubble sort, we were getting the largest element at the right position.
Here I am getting the smallest element at the right position.
Now in round two.
What's going to happen.
Pay attention.
In past two I will again go through this part of the array.
Now I will not take 11 because 11 already has reached to its right position.
If I will try to find out the minimum of this whole array, then I will get 11 again, which doesn't
make sense.
This time.
Again, I am going to make sure that I go through each and every element which were left.
So 11 is on the right position, right?
We don't know about other elements.
We will find the minimum and make sure that I put it to its right position.
So this time, what will happen?
We will have 11 here, 12 here.
And then we will have 25, 34 one minute, 90 and 22.
Now similarly we will do the third pass.
So in pass three we will try to find again the minimum element.
And we will try to sort it.
Now at this particular position, like in bubble sort, we were able to get each and every element towards
the last.
Here I am able to get each and every every element in the starting.
So I believe that I will need n minus one passes because again, if I am able to put n minus one element
at the right places, then the last element will of course be at the right place.
Okay, so pretty sure the basic idea is clear.
Now let us try to visualize this again.
Everyone through Hackerearth.
So let us go back here.
Yeah.
See, these are the elements.
Okay.
64 2512 2211 I think we have the one second.
The elements are different.
Let me just add like add the one we talked on.
So 25, 11, 34, 90 and 22.
Great.
So this is the example we took everyone.
Now we know that 11 is the minimum.
But to find that what I have to do I have to go to each and every element.
Right.
So let's go that first we will for each pass we will move left to right looking for next largest value
one that is found.
It will be swapped into its final position.
Okay I think it is doing the opposite way.
But let's see.
So it is doing it in the opposite position everyone.
So let us try to find the other visualization.
Just give me a minute.
So let us try to find some other visualization everyone.
Just a second visual algo selection sort.
So just to make sure that we don't get confused so we can do the same thing using this thing which we
discussed, it is just taking the Hackerearth implementation is just taking the maximum instead of minimum.
Okay.
So should be fine.
Let us just select selection sort here.
Let me zoom in and let us have the array defined here.
Great.
So let me make it 50.
I think there is a limit.
Should be fine.
See everyone this is the array.
I've just taken 50 instead of 90 because it supports till 50 only.
Okay so now pay attention in this.
I think it will be doing by the thing which we have discussed.
Now let me click sort okay.
So let us just make six here again.
So let us sort see this time okay.
The speed is very high.
One second.
So let us start from the complete start.
See 12 initially is the minimum.
Everyone.
So 12 is the minimum.
Now it is going and finding the other minimum.
This now 11 is minimum 3450.
It found that 11 is minimum.
So it is fact.
Okay.
Now see 11 is at the right position.
It is saying the one with red is the current minimum.
Okay.
In the next pass as we discussed it is taking 25 as the minimum.
And now it will go through the whole array to find out which is the minimum, which is or element which
is less than the 25.
So the way we start is we say that hey, I have the minimum.
Is there anyone else who is smaller than this particular element?
You go through the whole array and if you are able to find once you are able to find the smallest one,
then you just swap the same thing.
A very good way to remember this.
I will share after we see this definition, so that you are able to always understand what selection
sort is.
Okay, so let me just run this first.
So pay attention everyone.
We cannot make it lesser than one x so it should be fine this time 25 not 12 becomes the minimum 34
Four 5022.
So it will be swapped now.
Again, it will take 25 as the minimum and will start.
34 is not smaller.
9050 is not smaller 22 okay.
So see the understanding is also written here.
Set 25 as the current minimum.
Then iterate through the remaining unsorted elements.
We will not be taking them to find the true minimum.
Once you find the true minimum, just swap them.
So see pay attention.
Great.
So this time 22 is the true minimum.
Swap them.
Now we will take 34 as the minimum.
Find the true minimum.
Swap them.
Finally the last pass 50 and 34 doing it.
And now we have sorted nine n minus one elements.
The last one surely will be at the right position.
Okay, so great everyone!
I hope this visualization overall also helped you a lot.
Now what you have to do is to make sure that you are able to code this algorithm as well.
Okay, I want all of you to code these sorting algorithm from complete scratch, especially those who
are learning it for the first time, because you will get lots of confidence if it is taking time.
Don't worry.
Even when I was learning, it used to took me around half an hour to 45 minutes to properly code an
algorithm.
Okay, great.
So let me share another example as well, which I was saying.
Let's say there are multiple students like standing in a line okay, these are their heights.
So let's say students are standing like this and they are of this height.
The way I remember selection sort is that I am a teacher.
I don't know, this is a new class for me.
If I have to sort them out, what I will be doing, I will just shout that, hey, who is the smallest
person in the whole line?
This particular child will say that hey, I am the smallest.
Now if I have to do it manually, I will go to each and every children to see that.
Okay, he is the smallest one.
Once I found him, I am saying that.
Hey, you come to the first position.
You come in the very start of the line.
Once it happens, the line is going to be something like this.
So he is the smallest one.
Then larger, then the bigger one, then this, and finally this one.
Now again, teacher will say that okay, I have got the first person at the right position.
That is good.
Now who is the second smallest one?
And you will find the second smallest is this one.
Now you will say that.
Hey, you come to the second position.
Now you will ask the person who is at the second position to go to its position.
Right.
You cannot just ask him to go out of the line.
So just another intuitive example to understand.
Again, these are very helpful.
Normally to understand as well as when you are giving interviews.
If you are able to give this examples on the spot, it is very helpful for the interviewer to understand
that yes, this person has a complete knowledge.
Okay, so always make sure that you understand via example and visualization.
Great everyone.
So now what you have to do.
You will be given an exercise coding exercise in which you have to now do the selection sort from scratch.