INTRO Hello friends, welcome to Gate Smashers. In this video, I am going to explain insertion sort. And in this video, we will discuss all the important points related to insertion sort which are very beneficial for your competitive exams, even for your college and university exams. And I will explain insertion sort by explaining it with real life examples so that it will never go away from your mind. You will always remember how insertion sort works. So guys, like the video quickly and subscribe the channel. If you haven't done it yet, then please press the bell button so that you get all the latest notifications. Let's start. First of all, we will talk about insertion sort. If we have a random array, we have random elements in the array and we have to sort them and use them. So although we have a lot of sorting algorithms, but insertion sort is one of the majorly used algorithms. Why is it? You will know when we go about time complexities. First, let's talk about how it works. So look, I will tell you with a real life example. It works exactly like we play cards or deck of cards. So it works exactly like we play cards. I have taken some cards here as an example and I have put them randomly. Okay, randomly taken like this. Now let's say I picked the first card. We do it like this, we pick one card, like after dividing the cards. Like I picked the first card. Now what is the first card? Let's say 5. So what I have to do is how do we keep this 5? Like this. If you are left-handed or right-handed, now you will keep it accordingly. You have kept 5, then you picked the next card. Which card did you pick next? 6. So where will you keep 6? You will keep 6 like this on the right side. You keep it on the right side, you arrange it like this. Means you picked the first card, at that time there should be no comparison. As soon as you picked the second card, you compared one, that is it is bigger than 5 or smaller, then it is bigger, you kept it on the right side. You have to do it like this. Next, see which one you told, 10. Now what you have to do is when you have to compare 10, then you compared it with only 6. If it is bigger than 6, then you put it on the right side. Now there is no need to compare it with 5 because 5 and 6 are already sorted. So when 10 came, you compared with 6 and placed it on the right side of 6. Next, let's say the next card is 4. Now as soon as 4 came, you know that here is 10. So that means you compared it with 10 first, then on the left side of 10. Then 6 is there, then on the left side of 6. Then 5 is there, then on the left side of 5. Means you compared it 3 times, compared it with 4, 5, 6, 3 and then put it on the left side of them. So what we do with the cards in this way is arrange it. Let's say one more, 9. So what to do when 9 came? Because you know that before putting 9, all the elements that are in the last element are sorted. So as soon as 9 came, you have to compare it with 10 and put it on the left side of 10 because 9 is smaller than 10. So what you have to do in this way is arrange it. And this is how we do in real life, the same work that is insertion sort. Okay, so in this way you know it somewhere. You must have played a lot in lockdown. And anyway, engineering students can't stay. Nowadays, many games are going on online. But somewhere you must have faced this thing. Now let's talk here. First of all, we will talk here that how to start it. See this, in insertion sort, let's say we have this array. What is in the array? 40, 20, 60, 10, 50, 30. We have random elements. First of all, which came? 40. So simply place 40 without any comparison in the array. Now after that, which next element came? 30. Which next element? Sorry, 20. So as soon as 20 came, I have to compare 20 with 40. And if it is smaller than 40, then what I have to do is I have to put 20 on its left side and I have put 40 on this side. Getting the point? So how will your array look now? Your array will look, 20 came here, 40 came here. After that, which next element is there? 60. So first you will compare 60 with 40. So when you compare with 40, it is bigger than 40. So it is already in its exact position. Which next element is there? 10. So first you will compare 10 with 60. So if you compare with 60, it is smaller than 60. So 60 will come here, 40 will come here and after that 20 will come here. And on this position, the first position, who will come on that? 10. Means these 20, 40, 60, one by one moved ahead. So the elements are now yours. 10, 20, 40, 60. Getting the point? After that which element came to me? Then 50. So you have to compare 50 only with 60 because the previous element is already sorted. So you compared 50, so 60 moved ahead and 50 came to the 60 position. Then 30. As soon as 30 came, again compared with 60, then with 50, then with 40. So obviously this is its position. So will 60 move ahead 50 will move ahead 40 will move ahead And the position which will be empty, We will put 30. So how will the array be made? 10, 20, 30, 40, 50, 60. Getting the point? So in this way the array will be sorted. Now see how the algorithm of insertion and sort works. For J is equal to 2 to A length. Means where do I have to start from here? I will show you here again. From here you have to start J from this element. Getting the point? So J is equal to 2 to length. Length means till last it will work. A of J is equal to key. What you have done with A of J? You put it in key. Means to say that there was nothing in the first element. It does not need to be compared. That is simple 40 came. You put the next element in key. Let's say you took the key and put A of J in it. Means put 20. Now put 20. Now what we have to do? I is equal to J minus 1. What is the meaning of I is equal to J minus 1? We actually have to put this newly element, the key element in the right sequence. In the exact place. So I is equal to J minus 1 means where is the value of I starting from? I came to this point and J is already at this point. J minus 1 means I is at the previous one. Now see I is greater than 0. A of I is greater than key. Now check here. I will change the color. I is greater than 0. What is the value of I? 1 is greater than 0. Yes, true. And A of I. What is A of I? 40. So is 40 greater than key? What is the value of key? 20. Is 40 greater than 20? Yes, both the values are true. So in the case of and we check both. Then we will come inside. When we come inside, I have two lines. First, A of I plus 1 is equal to AI. Means What is the meaning of A of I plus 1? What is A of I? I plus 1 means it is talking about this. What did you put in this? A of I. Means you shifted 40 here. You shifted 40 at the next point and I is equal to I minus 1. Do I is equal to I minus 1. If you do I is equal to I minus 1, then what is the value of I? The value of I is already here. What was the value? It was 1. So where did it reach? It reached 0. Now when the value of I reached 0, then obviously it will come out of the loop. And when it comes out of the loop, then where will the key value be put? 0 plus 1 means at the place of 1. Means what is put at the place of 40? 20 is put and 40 is moved to the next one. Means whatever I had done to you in the cards, it works exactly the same. So 40 came here and 20 came here. 60 is here, 10 is here, 50 is here and 30 is here. Getting the point? Now I will show you one more thing so that you get it clear. 60 is already at the right position. Once it compares, it will come out of the loop. Why? Because A of I is greater than key, it will be wrong. Next let's say 10 came. Now as soon as 10 came, now what will happen? As soon as 10 came, now look carefully, what you have to do here as soon as 10 comes? See, I will show you again. As soon as 10 came, see what this algorithm is saying to you. I is equal to J minus 1. Where are you? J is yours here. Okay? You put A of J in the key. Now what did you put in the key? Put 10. Now see, I is equal to J minus 1. Means I is on your previous value. Now I is equal to greater than 0, yes, and A of I is greater than key. What is A of I? 60. Is 60 greater than 10? Yes. So what to do? A of I plus 1 is equal to I. Means this 60 went from here to here. Okay? A of I is put in place of A of I. What is A of I? 60, so put it on the next one. I is equal to I minus 1. I is on your previous value. Means it moved on 20. Now see, 20 greater than, it is running in loop, both these lines are running in loop in while. 20 is greater than 10? Yes. I value is greater than 0. Means loop will run again. And what will it do? 20 shifted from here and went where? This 20 shifted from here and went to this place. After that see, already when we did it here, 20 was here, 40 was here. Okay? Because previous one is already sorted. So 60 actually came here and 40 actually came here. So when we do next, 20 will go here. And when 20 came here, when it will come out of the loop, then what value is I plus 1? When I value becomes 0, then 0 plus 1 means what will it put in this position? It will put 10. So it means it will always be sorted like this. So if we have to find out time complexity of this, then see time complexity. So first of all let's talk about best case. So what is best case? Ascending order. When your data is already in ascending order. So in that case, see, if we talk about comparison first, then see how many comparisons will be there and how much swapping will be there. How many swaps will be there and how many comparisons. So see comparison, first 10 came, when 10 came, then there is no need of comparison, zero comparison. Then 20 came, so once compared, already it is in right position. 30 came, once compared, already it is in right position. 40 came, it is in right position. 50 came, it is in right position. Means how many times you have to compare, N-1 times, you have to compare. And see how much swapping happened. Is there any need to swap here? No, means I need zero swapping here. Here time complexity, what can you take out in best case? Write order of N, why? Because we can write order of N to N-1, it is upper bound. What is the value of upper bound? Order of N. So remember this point, it is a very very important point. Best case of insertion sort is order of N. And what happened to swapping? Swapping order of 1, you can write because there is no swapping here. So remember these two points. Then we have worst case here. This is more important, because somewhere here, we ask you upper bound. So upper bound means maximum value of time complexity, that is a worst case. But we also ask best case in exams. Now see in worst case, 10, 20, 30, 40, 50, 60. If we talk about worst case here, then worst case will be opposite to this. If you are given in this way, then call it wrong. Why? Because worst case will be this. Descending order. so decending order is the worst order so see we will comapre 60 and again find out in first case obviously we don't need to compare and swap next 50, one compare and one swap becoase 50 will come here and 60 here next 40, at 40 you did two comparison because with 60 with 50 and two swaps 60 50 and 40 will swap so you ahve 3 so you will have n=1 swap here so 0+1+2+3 upto n-1 so your series will be 1, 2, 3, upto n-1 to solve this series we use n(n-1)/2 we can write it as order of n2 because N square minus N divided by 2. So the bigger term among these, the dominant term is N square, so we write this as order of N square. So comparison order of N square, swapping order of N square. So we can write 2N square, but again we can write this as order of N square. It is again a very very important point. Remember this. In the case of descending order, worst order and in the case of ascending order, best order. And if we talk about average case, then in the average case, again your N square will be there. Because best case is more important. Now see, in worst case, N square comparison, N square swap. I have proved it to you. Now in best case, N comparison order of 1 swap. I have proved this to you. In average case, it will be same as in worst case. In last, your insertion sort is stable. Stable means simply this point is there, that the relative ordering of similar elements, means the non-distinct elements, nothing should change in their ordering. How? Let's see, if I take a simple example. 5, 2, 3, 5, 1. Let's say there are 2 5's here. Okay? Now what will happen? As soon as I got the first 5, I put it in position. If 2 comes, I put it in its left. Okay? 2 here, 5 here. Now give it like this. Name it 5A, its 5B. Means to say there are 2 similar elements here. If their position changes, a is here and b is here if they interchange if relative order of similar element changes then it's not stable now here 2 here and 5 here when 3 came here 2 here 3 here 5a here and 5b here next 5bb will remain at right only next 1, so 1 2 3 5a 5b when 5a was at left it will be in the left in the last, so means their ordering will not change. So if relative ordering does not change similar elements, means it is a stable. And what is the meaning of in place? Does it use extra space, insertion sort? No, the array which we have given, what is it doing in that array? It is comparing, swapping. Yes, some extra temporary variables like key, it is taking extra, but you can only write that order of 1, because you are not taking any n size, similar size array in it. Like we take in merge sort, here it is not doing that. And at last, let me tell you one more point, small points are asked in exams, in interviews, many people ask. So you should know from the point of view of interviews also. Next thing, it is also called online, online algorithm. What does online algorithm mean? As soon as element comes, what does element comes, it keeps sorting, it does not wait, like in selection sort, or in merge sort, it waits first, till all the array will traverse, will move all the array, then it will go and bring the smallest element forward. In bubble sort, what it does is it brings the biggest element to the last by going to the whole array, but what it does is it works immediately. Online means immediately, as soon as the array is given, as soon as the element comes, next element, you immediately arrange it and put it there, start it. That's why we call it online algorithm. So this is all about the insertion sort. Note all these points, it is very important. And this PPT I have made, of 4-5 slides, I will provide it in the description box. Thank You.