‫So now we're going to write our code for insertion sort.
‫We'll pick up where we left off in the last video with these two items swapped.
‫And I'll shrink this down to the bottom here to make room for our code.
‫We'll pass it the array and the size, and we'll start out with our for loop.
‫Notice that I is equal to one.
‫Normally we start at the beginning of the array at zero, but we're starting at this second item and
‫comparing it to the item before.
‫And we're going to set a variable temp to be equal to the value of that item at the index of AI.
‫And we're going to create a variable J that points to the previous item.
‫We'll do that like this.
‫J equals I minus one.
‫So we'll put that two back here and we're going to jump forward to this item because this is the first
‫value that we need to move.
‫This will be I and our for loop and this will be J.
‫And we'll say while temp is less than a ray at the index of J, that is this item.
‫And remember this will be temp.
‫So this conditional will be true for this iteration of the wild loop.
‫We'll set a ray at the index of J plus one to be equal to a ray at the index of J.
‫So that puts the value of four in that spot.
‫Then we need to put the value of three into this spot, and we'll do that like this.
‫A ray at the index of j equals temp and then we need to decrement J to move that over and we'll do that
‫like this.
‫J Minus, minus.
‫Now we'll run the while loop again.
‫And now temp is not less than a ray at the index of J.
‫So that breaks us out of this while loop and that three stays at that index.
‫So this code will almost work for insertion sort.
‫But there is an edge case that we need to address.
‫And to illustrate this, I'm going to take the first two items in the array and I'm going to switch
‫them.
‫So now we're going to take this second item and compare it to the item before it j will be set equal
‫to this index.
‫And then we'll go into the while loop.
‫We'll say while temp is less than a ray at the index of J and it is the case here we'll set a ray at
‫the index of J plus one to be equal to a ray at the index of J, which does this.
‫We'll set a ray at the index of J to be equal to temp, which puts this one in this spot.
‫But the problem arises with this line of code.
‫When we say J minus minus J is now pointing to the index of negative one.
‫And obviously we can't have an index of negative one in an array, so we have to add something to our
‫while loop.
‫J also needs to be greater than negative one, so both of these conditions need to be true.
‫Now, one of the things that is very important is the order in which you write this in the while loop.
‫If you write it like this, this test will happen first and you will be looking for an index of negative
‫one and you're going to get an error.
‫So you have to write it in this order.
‫So now that breaks us out of our while loop and that one stays at that index and now our array is sorted.
‫So that is all of our code for insertion sort.
‫We'll look at this code in a moment in VTS code.
‫And when we do we'll start out with an array that looks like this and then we'll run insertion sort
‫and we will sort that.
‫So now let's flip over and take a look at this.
‫So there is our function for insertion sort.
‫And I'll scroll up and in our main function this creates that array that we just saw and this calculates
‫the size.
‫And with this line, we'll run insertion, sort on the array with the size.
‫And this for loop will print out the sorted array.
‫So I'll run this.
‫And we have a sorted array one through six.
‫So that is our function for insertion sort.