Hi everyone, let's do this question.
You are given an array of integers.
Write a function that will take this array as input and return the sorted array using selection sort.
So in this question we are going to learn selection sort which is a very famous sort algorithm.
And again it's not very efficient but still let's it's very important to know.
So let's go ahead and learn this.
So we will be given an array of integers.
And we have to return the sorted array.
And the caveat is we have to use the selection sort.
Now let's go ahead and try to understand how we can approach this question.
And let's try to learn the selection sort.
So over here we have the array an array let's say.
And the selection sort works on the principle that in each pass where we iterate through the array which
is given to us, we will identify the smallest number and put it towards the front.
So in the first pass we will identify the smallest one.
And that would be put over here at index zero.
And then among the remaining ones again we will iterate through the array, find the next smallest one
and put it over here.
And so on and so forth.
So this is how this algorithm works.
Now let's try to see how it works and trace the algorithm.
So again we have our array over here.
Now let's write the indices of the given array.
So we have 0 to 5 over here.
Now we will be using two pointers.
So let's say one is I and the other one is J.
Initially I is going to point at index zero.
And we are going to say smallest is equal to this index zero over here.
And J is going to be the second pointer.
And we will say j is equal to I plus one which is the next index which is one over here.
So j is pointing at one.
Now we are going to keep I over here itself.
And then we will move J across the remaining part of the array in this manner.
And keep comparing the value at j and the value at the smallest index.
Now this is going to be modified if we find a value which is smaller than the value currently at this
index.
So let's just walk through the code and we will just understand it.
So at this point at index zero the value is four and j is pointing at index one.
The value is eight.
Now is eight less than four.
No it's not the case right.
So therefore we are just going to move J to the next index.
So we move j forward.
Now j is pointing at index two.
Now is the value over here which is two.
Is it less than the value at index zero.
Which is four.
Is two less than four.
Yes.
Yes two is less than four.
Therefore we are going to modify smallest and we are going to put the index two over here.
All right.
So this is this index over here.
So the index is tracked in the variable smallest.
Again we are going to move j forward.
All right.
Now Jay is pointing at index three.
The value is equal to six.
Now at index smallest which is two.
We have the value two is six less than two.
No it's not the case.
So we don't change this.
And we're going to just move Jay forward.
Now Jay is pointing at index four.
And the value over here is one.
Is one less than this two over here.
Yes it is less than two.
Therefore we are going to modify smallest to four which is this index over here.
So this is modified to four.
And again we move Jay forward and we get the value five over here.
And then we are going to check is five less than one.
No it's not the case.
So you can see we have moved across the remaining part of the array.
We have iterated through the array using the Jay pointer.
And we have found the smallest value which is equal to one.
So now we are just going to swap the value one with the value at index I which is this four.
Over here.
Now you can see effectively what we're doing is we are bringing the smallest value in the array to the
zeroth index.
So let's go ahead and swap these two.
So we get one over here and four over here.
Now our array looks like this.
So we have found the smallest value and we have put it at index zero.
So now we are going to move I ahead.
All right.
So I is now pointing at one.
Now what we are going to do is we are going to iterate through this part of the array, identify the
smallest value, and then put it at index one.
So this is how this proceeds.
All right.
So this is how the selection sort works.
So now again smallest is initialized as I.
So smallest is equal to one.
Now we have j.
So j is going to move through the indexes 234 and five.
All right.
So then when when we do that initially J is going to point at index two we see the value two.
And we will see that two is less than eight.
So we will modify smallest to two right.
So smallest will become two again J comes over here.
Now six is not less than two.
So J moves ahead J comes over here four is not less than two.
So again J moves ahead five is not less than two.
And that's it.
So J has reached the last index.
So therefore in this pass we will identify that the next smallest value is this two over here which
is at index two.
Now we are going to just swap the values at index I and at index smallest which is eight and two.
So these are two are going to be swapped.
All right, so we get two over here and eight over here.
Now our array looks like this.
So you can see we have identified the two smallest values.
And they are in the beginning of the array.
Now again we move I ahead.
So I is going to point at index two.
And now we are initializing smallest as two again.
And then we will use j.
We will iterate through this part of the array.
And then you can see that the smallest value is going to be this one over here.
Right.
So we will identify that smallest is equal to four by doing the same thing.
And then we are just going to swap the values at index I and at index smallest.
So these two are going to be swapped.
So we get four over here and eight over here.
So this is how the array looks like.
Now again I is going to be moved ahead.
Now I is pointing at index three.
So smallest is initialized to three.
And then we are going to use j to iterate through these parts.
And we find that the next smallest value is at index five.
Right.
So this value over here therefore we are just going to swap these two.
So small smallest will be found to be equal to five which is this index over here.
Now the values at index I and at index smallest which is six and five will be swapped.
Right.
So we will swap these two.
So we get five over here and six over here.
Now our array looks like this.
So you can see this part of here over here is now sorted.
Right.
Again we move I ahead.
So I is going to point at index four.
Now J is going to point over here.
Now we see that six is less than eight.
So smallest is going to be modified from 4 to 5.
So smallest will be equal to five.
And then we will just swap these two values.
So six comes over here and eight is over here.
And you can see we have got the array sorted.
So this is how the selection sort works.
Now you can see when compared with bubble sort it does lesser number of swaps.
So bubble sort swaps at every index every time it keeps swapping many times.
But over here we are just I we, we are moving through the array, finding the next smallest and then
swapping ones.
So this is how selection sort works.
Now let's take a quick look at the complexity analysis of this solution.
The time complexity of the solution or the selection sort is going to be of the order of n square.
And the space complexity is O of one, which is constant space.
Again, this is straightforward.
We have not used any extra or auxiliary space.
So that's why the space complexity is O of one.
Now let's try to understand why the time complexity is O of n square.
Now for this let's make a table over here.
So we have I and the number of comparisons.
Now initially we have seen that I is going to point at index zero.
And we have to make five comparisons.
Right.
Because J had to move from here then to here then to here, then to here and then to here.
And in each instance we made comparisons.
So that's one, two, three, four and five.
So when I is equal to zero we made five comparisons.
Later I moved to one and J moved from 2 to 3 to 4 to 5.
So over here you can see that's four comparisons.
So when I is equal to one we had to make four comparisons.
And in this way when I is equal to two we will have to make three comparisons etc..
Finally, when I is equal to five then we don't need to make any comparisons.
So if we take the total number of comparisons that we have to make that we had to make, it's going
to be one plus two plus three plus four plus five, right.
And again, if we generalize this over here we have five because the total number of elements was six.
So this five over here is actually n minus one.
So we are actually adding from one till n -1 or 1 plus two plus three etc. up to n minus one.
So this is the total number of operations that we had to do.
Now this series over here is equal to n minus one into n divided by two.
All right.
And this simplifies to n square minus n by two.
So you can see there is a n square term over here.
And that's why the time complexity is going to be of the order of n square.
Because this is the dominating uh factor.
Right.
So that's why the time complexity is of the order of n square.
Now, if you don't know this, this is something that you should know if you take the numbers from one
to x, for example, one plus two plus three etcetera up to x.
In this case this sum over here is going to be equal to x into x plus one divided by two.
So this is something that you should know.
All right.
So if you don't know it make don't know it make a note of it.
Because it's going to be useful in many cases.
Now for example let's try this out.
So one plus two plus three up to five.
All right.
So this is going to be equal to five into five plus one which is six divided by two.
So this simplifies to 15.
Now if you add one plus two plus three plus four plus five you will get 15.
All right.
So in a similar manner over here instead of x I am just writing n minus one.
So this is n minus one into n minus one plus one which is n itself divided by two.
So that's how we are getting this over here.
And this when you expand this bracket you get n square minus n by two.
And then two is a constant.
So we neglected and among n square and n n square is the bigger factor.
So we can just neglect this.
And that's why we can say the time complexity of this solution or the selection sort is of the order.
Rough n square.