In the next video, you will learn how to write the pseudocode for Insertion sort algorithm.
Video Transcript:
Now let us take a look at a simple pseudocode for the insertion sort algorithm. So you can see that here I have declared a variable I as well as a variable j and I am initializing I with one and j with I. Let us leave the code here and consider a situation where my I is equal to three. In that case, my j will also be equal to I and will begin from three. So suppose that I'm in the third iteration and my I is currently here, I is equal to j is equal to three. In that case, what I have to do is that I have to compare all the elements towards the left of this ith element and see if any one of them is larger than my A of i. If that is the case, I will swap them. So here what I'll do is that I have I is equal to j is equal to three. So here I will compare A of j minus one and A of j, that is A of two and A of three.
Now I'm comparing a of two and a of three. In case I find that A of two is greater than A of three, then I will swap these two elements, which is what I am doing here in this statement. In the next statement, I would decrement my j to j minus one. That is, in my next step my j would come here j equals to two. I would then repeat the same procedure, that is, I would compare A of j minus one and A of j, which is what I'm doing here in this while statement. So if I look at the array here, I would be comparing A of j minus one. My j here is two. Two minus one is one, that is I will compare A of one and A of two. In case I find that A of one is greater than A of two, I will swap these two elements, which is what I'm doing here. After swapping, I will decrement my j and make it equal to j minus one. So in the next step my j would come here, that is, at j equal to one. I would repeat the same procedure again and check whatever elements are there towards the left of this particular jth element.
That is, I would compare A of j minus one, that is A of zero with A of j, which is one. In this particular case, in case I find that A of zero is greater than A of one, I would swap them as I am doing in that statement, and I would decrement my j pointer. So when I finally decrement my j pointer, my final j value would be j equal to zero and it would point here. Here I would see that there is no element left to compare. So this would mean that I have reached the end of this particular iteration. So my J will essentially need to be just greater than zero. That is, my J will essentially need to just terminate at one itself. So let us revisit this code again. I started my I from one, that is, I will start at index number one. Then I'll declare another while loop here. And before that, I would declare a variable j, which will also start from I. The j will now go on from I till the end, which is while it is while j is greater than zero. And in each step, I will compare my A of j value with its left value. That is, A of j minus one will be compared to A of j. In case A of j minus one is greater than A of j, I will swap them and I would decrement my j pointer. Moreover, as soon as this is over, I would also increment my I pointer so that I would now move on to the next element and repeat the entire procedure for the next element. So this was how insertion sort works. So now why do you think have we used a while loop here? Couldn't have we used A for loop? You would see that basically I need this particular while condition to execute only while my J is greater than zero. That is, I have not reached the end of my array and my previous element is greater than my current element. So basically, as soon as I encounter an element which is less than my current element, I would simply go out of this while loop. So this is the basic reason why we have used a while loop here, so that we go into the while loop only when this condition holds. So.
Now that you have understood the pseudocode for insertion sort algorithm, the Java implementation in the video below shall be a cake-walk for you. Please download the following java file for your reference.
Transcript Summary:
Pseudocode for insertion sort algorithm involves initializing variables and .
is the index of the element being sorted and starts from and moves towards the beginning of the array.
The elements towards the left of the element are compared to the element.
If any element to the left of is larger than A of ,they are swapped.
The while loop is used to compare elements until is greater than zero and the previous element is greater than the current element.
As soon as an element less than the current element is encountered, the while loop is exited.
pointer is incremented to move on to the next element and repeat the entire procedure.
The while loop is used because it executes only while is greater than zero and the previous element is greater than the current element.