Welcome back.
Let's now go ahead and write the code to implement the selection sort, which we have discussed in the
previous video.
Now again for this we need a function.
Let's call this function selection sort itself.
Now this function is going to take in the array which is given to us.
And let's call this array numb's.
Now inside the function, what we are going to do is we're going to have a for loop and we'll have two
pointers I and J.
So let I is equal to zero I less than numb's dot length.
I plus, plus.
So we are using AI to traverse or iterate through the array which is given to us.
And now let's have a variable.
Let's call it smallest, because we have to identify the index of the smallest in every pass through
the array.
And then as we discussed, we are going to move the smallest to the friend.
So that's how we are going to implement this.
So initially let the smallest be equal to I.
And then we'll have one more nested for loop over here.
So for let j is equal to I plus one j less than.
Numb's dot length.
J plus plus.
So we are going to check whether numb's at J is less than numb's at smallest.
So if numb's at J.
Less than Numb's at smallest.
If this is the case, then we have to reassign smallest to j.
So we can say smallest is equal to j.
All right.
So once you are out of this so for one value of I we are traversing through the remaining part of the
array.
And we are identifying the lowest value starting from I.
All right.
So once we have identified the smallest now we will just check if I is not equal to the smallest.
Right.
So that means that another index is the smallest.
And then we have to swap I with j with smallest.
So in this case we have to swap I and smallest.
All right.
So let's do that.
So let's use a temporary variable.
So let temp is equal to numb's at I.
And then we can say numb's at I is equal to numb's at smallest.
And numb's at smallest is equal to temp.
And that's it.
Now once we're out of this for loop we just have to return the array.
So return numb's.
And that's the implementation of the selection sort.
Now let's go ahead and test our code.
So let me just run it.
So for this we'll call our function.
And let's pass in an array to it.
Let's say we have 432 and one.
And let's run our code.
And you can see, yes, we are getting one, two, three, four which is sorted.
Right.
So that's working.
Let's try another array.
So let's say we have five over here and we get 12345.
And what if we have duplicate elements.
Let's say we have two also over here.
Then we get 122345.
So yes our selection sort is working.
Now let's take this example and let's just walk through the uh code.
So let me just make this smaller so that it's easy to walk through.
So let's say four three, one and five is given to us.
We can see we are getting one, three, four, five.
So let's see what's happening over here.
So let me grab a pen for this.
All right.
So this is the array 431 and five which is given to us.
And let's write the indices.
So we have 012 and three over here.
Now when we call the function first I is going to point to here.
So I is equal to zero.
And we are inside the for loop.
Now smallest is going to be equal to I which is zero.
So smallest.
Is equal to zero.
And then we have this for loop over here.
So J is going to be equal to I plus one which is zero plus one which is equal to one.
So j is over here.
And then we are checking is numb's at j which is three is three less than numb's at smallest which is
four.
Yes three is less than four.
So we are going to change smallest to j which is one.
So smallest becomes one.
And then again j moves forward.
So J comes over here.
And then we are checking is numb's at j which is one is one less than numb's at smallest which is three.
Yes one is less than three.
So we are going to say smallest is equal to j which is two over here.
Right.
So smallest is going to be equal to two.
And then again we come over here we move j forward.
And then we are checking is numb's at J which is five is five less than numb's at two which is smallest.
Right.
So numb's at smallest is one.
Is five less than one.
No that's not the case.
So we don't update smallest.
And then we come out and over here we are going to check I is equal to zero.
And we are checking whether I is equal to smallest.
No it's not equal right.
So I is not equal to smallest.
So we come inside and we are going to swap the values at I which is four and the value at index smallest
which is two.
So these two values are going to be swapped.
So the array becomes 134 and five.
So this is after one pass.
Now again we come over here and I is going to be incremented.
So I is going to be equal to one.
So this is I.
And again smallest is equal to I.
So smallest is equal to and again this index is one right.
So this is 012 and three.
So smallest is going to be equal to one.
All right.
And then over here, when we come over here, we say j is equal to I plus one.
So let me just clean this up a little bit.
So I j is equal to I plus one.
So we get j is equal to one plus one which is two.
So j is equal to two index two.
So j is over here.
And then we come over here and we are checking is numb's at J which is four is four less than numb's
at smallest.
Smallest is one at one we have three.
Is four less than three.
No that's not the case.
So again we come over here and J is moved ahead.
So we come over here and then J is pointing to five.
Again we check is five less than three.
No that's not the case.
So when we come over here we will see that I is equal to one.
And smallest is also equal to one.
So we don't swap.
We don't come inside over here again.
When we come over here we're going to increment I.
So I now is going to point to two.
Let me just clean this up a little bit.
So I is going to point to two.
So we have I over here.
And then again we say smallest is equal to two.
All right.
We come over here J is going to be equal to three.
Now we are again checking is five less than four.
No that's not the case.
So we don't change this.
We come and then we don't have anything.
J does not have any more place.
Right.
So this is already at index three.
So we come out of this for loop.
And over here we are checking if I is not equal to smallest but they are equal.
So we don't swap.
And again we come over here and I is incremented.
So I comes over here.
All right.
So I is at index three and smallest is three.
And j is going to be equal to I plus one which is four.
Right.
And again this does not this is not true.
So we don't go inside over here.
And we see that I is equal to smallest.
So we don't swap.
And we get 1345.
And we are just returning this over here.
So this is how the function works.
Now let's take a quick look at the space and time complexity of this solution.
The time complexity of this solution is of the order of n square.
Right.
So we can see we have a nested for loop right.
So there is a for loop over here and a for loop over here.
So that's why we have an O of n square time complexity.
And again we have discussed it in the previous video.
If we have four, three two and one right.
So initially I is going to be over here.
And then we are going to have comparisons.
We are going to check this value with these three values to identify which is the smallest.
So we have three comparisons.
And then when I is over here we are going to have two comparisons.
And then when I is over here we are going to have one comparison.
So if this was of size n then the first in the first case we will have n minus one comparisons.
Then we will have n minus two comparisons.
And this will keep happening till one.
So this is a total number of operations which we have to do for this algorithm.
And we have seen that this simplifies to n minus one into n divided by two.
And when you simplify this there is a n square term which is the dominating term.
And that's why the time complexity of this solution is of the order of n square.
And the space complexity is constant space.
Because as you can see, we are not using any extra space.
We are not creating a new array or any any other data structure, etc..
Right.
So the space complexity over here is O of one.