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 insertion sort.
So this question is about insertion sort.
So we will be given an array of integers.
And we have to just return the sorted array.
But the caveat is that we have to use insertion sort.
So let's go ahead and try to learn insertion sort in this video.
Now the insertion sort works on the principle of dividing the array which is given to us into two parts.
Now the two parts, one part of the two parts, one part is going to be sorted and the other part is
not sorted.
And then we will just pick one element at a time from the non sorted part and insert it into its correct
position in the sorted part.
So this is how the insertion sort works at a high level.
Now let's try to understand this.
So again what is the sorted part.
Let's say the array is 432 and one.
Now we are going to split the array into two parts.
And this is going to be one part.
And this is the other part.
Now if we have only one element then this is sorted right.
Because it's just one element.
That's why this part is going to be sorted.
And this is the unsorted part because we don't know whether this is sorted or not.
And then we are going to pick one element at a time and insert it into the sorted part and expand the
sorted part.
So this is how the insertion sort works.
Now let's try to take an example and walk through it so that we can understand this thoroughly.
So I have an array over here 73851.
Now this part is going to be the sorted part which has just one element.
And this is the not sorted part.
All right.
Now let's keep this aside.
Now this is the array with which we are dealing with.
Now.
We are going to have a pointer to iterate through the array which is given to us.
But we know that this part is already sorted.
So we are going to start over here which is at index one.
So I is let I is equal to one.
So I is starting at index one.
Now the value over here is three.
So we are going to take out this value and store it in a temporary variable.
Now we are going to have one more variable let's call it j.
Now j is going to be equal to I minus one which is the previous element over here.
So j is over here at index zero.
Now we are going to check is the element in the given array at index j.
Is it greater than the temp value which is three.
So is array at j greater than temp or three.
Now in this case we have seven over here.
And yes seven is actually greater than three.
So again what what is it that we are trying to do.
We are trying to insert three into the sorted part which is just seven at this point.
Now we have seen that the seven is greater than three.
So we cannot leave it like this.
Right.
So seven comma three.
The order would be wrong.
So what do we do.
We are going to shift this seven to the right.
So we're going to shift this to the right.
And we have seven over here.
Now it looks like seven comma seven.
And then J is going to be decremented.
So j becomes minus one.
Now because J is not greater than zero any longer, we know that we have nothing over here, and therefore
we are going to insert this temp value at r I at j plus one and minus one plus one is zero.
So therefore we are going to insert three at index zero which is over here.
And we get three over here.
So now you can see that the sorted part is three comma seven.
And the unsorted part is eight comma five comma one.
And you can see that the sorted part has increased in length.
So what did what did we actually do.
We took this one element and we inserted it in the correct position in the sorted part of the array.
So this is how the insertion sort works.
So let's make some space over here.
Now let's proceed.
Now initially I was over here right.
So again now I is going to be over here.
And remember this is now sorted.
So this is the sorted part and this is the unsorted part.
So I is going to increment from 1 to 2.
That is I is going to point at the beginning of the unsorted part.
Now we take this value eight.
And we are going to store it in a temp value.
And we have to decide where to insert this eight in the sorted part.
Now J is going to be the other pointer and j is going to be equal to I minus one.
So j is going to be equal to one okay.
So it's going to point at index one.
Now we are going to check is the value at index j.
Is it greater than the temp value or is seven greater than eight.
That's not the case, right?
Seven is not greater than eight.
So we can understand that already this element is at its right position.
We don't need to keep checking towards its left, because we know that this part is already sorted.
And because this value eight is greater than seven, or because seven is not greater than eight, so
eight is already at its correct position and we can leave it as it is.
Now we see that the sorted part has again increased.
Now three, seven and eight are sorted and five and one are not sorted.
So let's make some space.
We again increment I.
So I is going to point at index three and j is going to point at index two.
Okay.
So this is two and this is three.
Now this value over here will be stored in our temp variable.
And again we will check is the value at index j greater than the temp value or is eight greater than
five.
Yes eight is greater than five.
So we cannot leave it like this right.
So we're going to shift eight towards the right.
So we're going to move it towards the right.
And we say j at J plus one which is this over here is going to be equal to array j.
So we get eight also over here.
And then we are going to decrement j.
So j comes over here.
And again we're going to check is the value in the array at index j greater than temp or is seven greater
than five.
We see that's yes that's the case seven is greater than five.
Therefore we cannot insert the element which we are looking at which is five over here.
Right.
We cannot insert it over here because this is greater than seven is greater than five.
So we cannot it cannot insert five over here.
So we're going to move seven to the right.
All right.
So we are going to say array at j plus one is equal to array at j or over here we are going to overwrite
it with seven.
And then we are going to decrement j.
So j comes over here.
And again we are going to check is the value at index j greater than five.
So is three greater than five.
No that's not the case right.
So we no longer need to move three to the right.
But we can insert the five over here.
We can insert it over here at this position.
And again so for this we will just say array at j plus one is equal to five.
And seven is already over here.
Right.
So we are not losing any value.
Right.
So over here we were either to move three to this place or we were to insert five over here.
Now at this point we can insert five over here because we have seen that three is not greater than five.
So we get five over here.
And then our array looks like this.
Now we have 3578 and one.
And this is the sorted part.
And we just have one element over over here in the unsorted part.
Now I is going to point at that element.
And then j is going to point at the previous element.
And again we're going to check is the element at index j greater than the temp value.
Yes eight is greater than one.
Therefore we are going to move eight to the right.
All right.
So let's do that.
So we get eight over here and we decrement j again we are going to check is seven greater than one.
We see.
Yes that's the case.
Therefore we move seven to the right and we decrement j by one.
So we get j over here again we're going to check is five greater than one.
Yes that's the case.
Therefore we're going to move five to the right.
And we decrement j by one.
Again we are checking is three greater than one.
Yes that's the case.
So we move three to the right and we decrement j by one.
And now j becomes minus one.
So j is no longer greater than equal to zero.
Therefore we know that we can just insert the element at j plus one.
So that's minus one plus one which is index zero.
So at index zero we're going to insert the temp value which is one.
So we get one over here.
And you can see that our array is now sorted.
We have 1357 and eight.
So this is how the insertion sort works.
Now what about the complexity analysis of this solution.
Let's take a look at it.
Now let's say the array which is given to us is one, two, three, four.
This is the best case scenario for the insertion sort, because initially I is going to point at index
one right over here.
And we will just make one comparison.
And we will see that it's in the correct position.
Then I is going to move to index two.
We will make one comparison and we see that it's in the correct position.
And again we move I to index three.
We will make one comparison and we will see that it's at the correct position.
So we only have to do n operations or n minus one operations to be exact.
So n minus one operations.
So we can say that the time complexity in the best case is of the order of n because this is just a
constant.
So we avoid this.
Now in the worst case let's say the array looks like this 432 and one.
So I initially would be at index one.
And we would have to make one comparison.
All right.
And this changes to 342 and one.
And then I would be at index two right which is over here.
And then we would have to make two comparisons.
Right.
Because we'll have to get two over here.
So it would be 2341.
And then I is going to be over here at index three.
And then we'll have to do three comparisons.
Right.
So this is the worst case.
So over here three note is that we have four elements.
That's why we stopped over here with three comparisons.
So three over here is actually n minus one.
So the total number of operations that we have to do is one plus two plus etc. up to n minus one.
Now we know that one plus two plus three, etc. up to n is equal to n into n plus one divided by two.
Now over here we just have to add till n minus one.
So instead of n we can write n minus one over here.
So we just have to change this n to n minus one and this to n minus one.
So this over here sums up to n minus one into n minus one plus one by two which is equal to n minus
one into n by two.
And if you expand this you will get n square minus n by two.
So you can see that there is an n square term.
So that's why the time complexity, the worst time complexity is going to be of the order of n square.
Now we have seen that the best case is O of N, and the worst case is O of n square.
And the average case of the time complexity for the insertion sort is also going to be of the order
of n square.
Now what about the space complexity?
The space complexity of this solution is O of one because we are not using any extra space.