Welcome back.
Let's now go ahead and write the function to implement the insertion sort, which we discussed in the
previous video.
And we will call this function insertion sort.
Now this function is going to take in an array.
And that's the array that we need to sort.
Now remember how this works is that we're splitting the array into two parts.
For example, if the array which is given to us is four, three, two and one, then we are going to
consider this over here as the sorted part.
And then this is the not sorted part.
And then we are going to pick one element at a time from the not sorted part, and then insert it at
the correct position into the sorted part and expand the sorted part.
So that is how this proceeds.
So you can see that the not sorted part starts at index one, which is this index over here.
So that is why we are going to have a for loop.
And in the for loop we are going to start at index one.
So for let I is equal to one I less than array dot length.
I plus, plus.
All right.
Now, inside the for loop we have seen that we'll have another variable j.
So j is going to be equal to I minus one.
So j is going to start at the index before I.
So j let j is equal to I minus one.
And let's also have a temporary variable.
Let temp is equal to array at I.
So we are using this to store the value in the array at the ith index.
Now again let's just try to take an example and walk through this over here so that we can understand
what's happening.
So let's say the array is 3578 and one.
And let's say we have done already some sorting operations.
And now I is over here.
All right.
So I'm taking this example I over here to make it more clear.
So this is 01234.
So let's say I is equal to four.
All right.
And then we want to insert this element over here in the correct position of this part.
So this part is the sorted part.
Again I'm repeating we are considering the case where the array was looking something different in the
beginning.
And we already sorted right.
For example we will start with I over here and then we move over here.
Then we move over here and then I will finally be over here.
So we are just taking that instance, that snapshot to understand what's happening over here.
So J is going to be equal to I minus one.
So J is going to point to this index over here.
And then we are going to check whether whatever is over here right.
Whether whatever is over here is greater than this value.
So that is what we want to check.
So again that's why J is going to be I minus one which is this index.
And then this is going to happen as long as j is greater than zero because this is over here.
Right.
Greater than equal to zero.
So we are going to have a while loop for this.
So let's go ahead and write that over here.
All right.
So we can say while.
J greater than or equal to zero.
And then there is one more condition, right.
We need to keep checking only as long as our A at J.
Is greater than temp.
Now why is that?
So if we see that the previous element is not greater.
For example, let's take an example to understand this.
Also, let's say the array is five seven and let's say over here we have eight.
And let's say I is over here.
All right.
Now this is the sorted part.
So because I is over here this is the not sorted part.
Now we are trying to insert this in the correct place in the sorted part of the array.
Now we are seeing that let's say array at J which is what we have over here.
We see that it is not greater than this value which is there in temp.
Right.
In that case, these this is already sorted because we know this part is anyway sorted.
Right.
So we don't need to keep checking.
So that's why we can stop when array at j is no longer greater than temp we can stop.
So that's why this is the condition.
Now, once inside the while loop.
Let's continue.
What is it that we have to do?
So J is greater than or equal to zero and array at j is greater than temp.
So in that case we are going to shift the value of array at j and put it to array at j plus one.
So we're going to say array at j plus one.
Is equal to r8 j.
And then we're just going to decrement j.
So j minus minus.
And this keeps happening.
Now we will come out of the while loop in two ways.
Either j is no longer greater than or equal to zero.
In that case we have to insert.
So j will be minus one right.
So in that case we have to insert the value the temp value at the zeroth index.
So we can say array at j plus one.
It is minus one plus one, which is zero.
So j plus one is equal to temp.
Now the other possibility why we came out of the y loop is that r I j is not greater than temp in that
case.
Also we just want to insert temp to arrive at j plus one right.
So let's try to understand this.
We'll take in we'll take an example and walk through this to understand this.
Well now that's it.
So once this is done we just have to return the array.
And it is done.
Now let's just test this and then we will take a sample input and walk through the code.
So let's call the function.
And let's say the array is four, three, two and one.
And we're calling the function.
And yes, you can see we're getting one, two, three, four.
That is it sorted.
Now let's take this example and try to understand what's happening over here.
So initially the array is 4321.
So let's write it over here.
And we come over here, I is going to point at index one.
This is one.
This is two.
This is three.
This is zero.
So I is equal to one.
J is going to be equal to I minus one which is zero.
So Jay is pointing to zero and then temp is going to be array at I which is this value.
So this value is stored in temp.
And then we see that j is greater than or equal to zero and array at j.
Which is what we have over here is greater than temp.
So yes we come inside the while loop.
And then we are going to say array at j plus one is equal to array at j.
So this is j.
So j plus one is what we have over here.
This is going to be array at j which is four.
So basically we are shifting the value over here.
And this is going to change to four.
Now it's looking like 442 and one.
And j is decremented.
So j becomes minus one.
And when we come and check over here is j greater than equal to zero.
No that's not the case.
So we are out of the while loop and then array at j plus one.
That's minus one plus one.
This is going to be zero.
So array at zero is going to be temp.
And we had stored the value three in temp.
So we are going to insert three over here.
And now the array looks like this 342 and one.
Now you can see that this part is sorted.
So the sorted part has expanded.
All right so this part is sorted again.
We come over here and I is incremented to two.
So this is two right.
This is index two.
So I is going to point over here.
And J is going to be I minus one which is over here.
So J is going to point at index one.
Now we are going to store the value at rate I, which is this two.
This is going to be stored over here.
Now we enter the while loop.
Is J greater than zero.
Yes j is equal to one.
So that's greater than equal to zero and array at j.
Is it greater than temp.
Over here we have four and four is greater than two.
So yes this is truthy.
So we come inside and then we are checking is array at j.
We are going to assign array at j plus one which is over here is going to be equal to array j.
So we are shifting it in this direction.
So this value is going to be four.
And then we are doing j minus minus.
So j is going to point to index zero now.
So let's just wrap this.
And then again we check is j greater than or equal to zero.
Yes.
This is zero.
Right.
And then is j which is three.
Is it greater than temp which is two.
Yes that's also true.
So we come inside and then we are saying array at J plus one which is zero plus one which is one.
So that's index one.
So this over here is going to be equal to array AJ which is this value.
So we are shifting this in this direction.
So we are getting three over here.
So we'll get three over here.
And then we have three three and four and j is decremented.
So J comes over here which is minus one.
Again when we check is j greater than or equal to zero it's false.
So we come out and then minus one plus one is again zero.
So array at zero is going to be temp.
So this is over here going to be two.
So we get 234 and one.
So you can see that this part is sorted and it's expanded expanding.
All right.
Now again we are going to take our I equal to three.
So 0123.
So this is going to be I.
And then we'll have J over here.
And then what will happen inside the while loop?
We'll just shift, right?
So we'll shift this over here.
This is going to be four.
And then we come over here J is going to point over here again we shifted.
This is going to be three.
And then we shift J over here.
This is going to shift to two right.
Because this is one.
So this is going to be two.
And then J will come over here which is minus one.
So that's why at minus one plus one that's zero.
At the index zero we will insert the temp value.
And that's one.
So that's how we get 1234.
Now let me also take one more other case.
Let's say we are having the array 432 and five.
So let's take that example also.
So let's just clear this up.
So the example is let's have four, three, two and five.
All right.
So let's just walk through the code and see what's happening.
So we are inside the function.
Again I is going to be equal to one.
So this is zero.
This is one this is two this is three J is going to be equal to I minus one.
And then we see that j is greater than or equal to zero.
And I and j which is four is greater than temp which is three.
So three is going to be in temp.
So what are we going to do.
We are going to shift in this direction.
That is array at j plus one is equal to j.
So this is going to be equal to four.
And then j minus minus.
So j becomes minus one.
So we are going to say array at j plus one which is zero is equal to temp which is three.
So we are getting three over here.
So now it looks like this 342 and five.
So the sorted part has increased.
Again I is going to point to two.
J is going to point over here.
And then we shift this.
So we get four over here J comes over here and then we get three over here J comes over here.
And then this two is going to be inserted over here.
So we'll get 234 and five.
Again I is going to point to this index over here which is three.
Right.
So I is going to point to three J is going to point to two.
So this is J this is I.
At this point we will see that j is greater than zero.
So that's true.
But is array at j greater than temp.
So is this greater than temp.
No that's not the case right.
So this is not greater.
So we will just come out of the while loop.
And then over here we'll just say array at J plus one is equal to temp.
So j plus one is five itself.
And five will be replaced with five itself.
So nothing changes.
And then we we we are we are done.
Right.
So we don't need to continue checking over here because we know that this part is sorted.
So if this is greater than this, which is the greatest value in the sorted part, it will be greater
than every value.
So its correct position is over here itself.
And then we stop.
So this is how the insertion sort works.
So basically we are splitting the array into two parts into the sorted part and the unsorted part.
And then we are trying to increase the length of the unsorted part.
Now over here you can see that we have nested loops.
So we have a for loop over here.
And then we have a while loop over here.
So that's an indication why the time complexity is of the order of n square.
Right.
The time complexity of this solution is of the order of n square.
And again we have taken an example also.
For example let's say it's 432 and one.
So initially I is going to point over here and we are going to make one comparison.
Then we will shift it.
So we'll have three over here and four over here.
And I is going to be over here.
Then we will make two comparisons.
Right.
So that's plus two.
And then when I comes over here we'll have two three and four over here.
And one is over here.
And we'll have to make one, two and three comparisons.
So that's how we've seen that mathematically.
Also it's going to be O of N square because it's nothing but one plus two plus three etc. up to n minus
one.
And this sum will have n n square term because this can be simplified to n minus one.
Into n divided by two.
And when we simplify this there will be an n square term.
So that's why the time complexity of this solution is O of n square.
And the space complexity is going to be O of one because we are not using any extra space.
So this runs in constant space.
So the space complexity of this solution is O of one.