Hello everyone and welcome to this second video in this video series on sorting. In the last video we saw how to apply bubble sort to sort n given elements and in this video lecture we are going to see the insertion sort technique to sort the given data. I am Vinit Thribuwan from Department of Computer Science and Engineering here in Valchand Institute of Technology, Solapur and welcome to this video lecture. So by the time you watch the video and you reach the end of this video you will understand the insertion sort algorithm and we are also going to see how to apply this sorting technique to sort the given set of integers. So before we move on with learning sorting algorithms and techniques I strongly encourage you to revise the concepts of handling arrays and loops in C language. So the videos on using or how to use arrays and how to use loops in C are already present on WIT PLC channel. You can watch the same before learning how to sort data using sorting techniques. So talking about insertion sort once again it is one of the simple sorting technique. Again it is also based on comparison quite similar as bubble sort is also based on comparisons so also insertion sort is also based on comparison. Here one element is considered in each iteration to find its correct sorted position that is the position that it belongs to in a sorted array. How do we follow the sorting in insertion sort? Insertion sort uses the mechanism when we sort a handful of playing cards by placing a card in its proper place. Say for example you are playing cards with your friend and you draw n number of cards say for example 7 cards from the pack. Now each of this card has a particular value and you want to sort this set of cards that you have in your hand according to its order. So you choose one card and try to put it by shifting the other cards to the right or to the left. Similarly after you follow this procedure for 6 times you will come to see that all the 7 cards that you have in your hand are in its correct order. Insertion sort follows the same procedure. Let us see its algorithm and its pseudo code. In insertion sort we start scanning the elements considering one element at a time. When we scan the next element if the next element is less in value than the current element we place the next element in the correct sorted order by shifting the sorted elements. We continue scanning the unsalted array till all the elements are placed in its sorted order. You will get a clear understanding once we see the pseudo code how insertion sort is actually applied to a given set of integers. Say for example we have an array A of size n and then we are scanning the elements from 0 till n minus 1. Now I set the ith element as and the value of the ith element to 10 and then I am scanning again the element for j greater than 0 till the value that is stored in temporary is less than j minus 1. Now if this value becomes small the value at j minus 1 index it becomes small then all the elements will be shifted all the elements will be shifted just to make place for the value that is stored in the temp variable. And once they are shifted then at jth location the value stored in temp variable will be inserted. Now let us see how insertion sort exactly works. We shall see a quick simulation of insertion sort. This is hacker earth.com platform which provides us a visualizer or a simulator of various sorting techniques and this is the simulator for insertion sort. Now let us take a few random variables or values. I have these five values and let us check how insertion sort exactly works. Now these green highlighted values are the values which are considered to be sorted. Now let us scan the rest of the array. So we see that the array or the element 3 has now been put in its right position and now we want to put the element which is highlighted in the blue that is value 2 to be put in its right position. So we are shifting elements 5 and 3 just to make sure that the element 2 in its is in its right place. Now we see that the sub array from 0 to 1 is in the sorted order and it is highlighted by green color. Now we want to put element with the value 1 in its right position. So we shift the elements 5, 3 and 2 to the right just to make place for element with value 1. And now we see that elements 1, 2, 3 and 5 are in its sorted position. Now element 4 with the value 4 will be shifted till its value is less than the element at the left. So it is shifted at one for one position and since this value is greater than the value at the left we will not shift the elements and it finds its final position in the array and we are done with the sorting. This was the simulation of insertion sort. So at this point in time I want to pause the video and I want to ask you a question that how many comparisons are required if you want to sort an array of n elements by using insertion sort. Pause the video for a few minutes and answer the question. So if you have clearly calculated and seen the pseudo code and the algorithm of insertion sort you will come to see that n squared comparisons are required to sort an array of n elements by using insertion sort. Now say for example you want to put the element which is at the nth location in its correct place and for that you want to shift all the n elements. That means the element is traversing through the array and then finding its correct position. Here if you calculate you will come to know that you will require n squared comparisons. That is why for sorting an array of n elements using insertion sort we need n raise to 2 or n squared comparisons. These are the references that I have referred to for the video lecture. You can also refer to this article which gives you detailed information regarding the analysis of insertion sort which is not in the scope of this video but which will help you to understand insertion sort in detail. Thank you very much.