Last time, we learned how selection sort works and we learned that's also in order n-squared sorting algorithm. This time, we'll look at another sorting algorithm called insertion sort. In the reading that covers insertions sort, is the same reading you've already seen for the other two kinds of sorts that we've discussed so far. Our problem is still the same but we want to sort an array of values. Another solution to that problem is insertions sort, and there are online visualizations. We'll look at one before we finish this lecture. So let's learn about insertion sort. I've jumped right to the insertion sort function in the code we've been using for the last few lectures, here's how insertion sort works. We're going to process the array from left to right again, so our sorted portion of our array will grow from the left towards the right, so we're pushing the smallest elements over to the left. The outer loop goes starting at K equal 1 because the zeroth element is already sorted remember, and it will go while k is less than count. So we're going to go all the way to the last element in the array. We set a temporary value as array k. Now remember, as we execute this loop as we move along in this outer loop, k is the leftmost part of the unsorted portion of the array. K minus 1 and everything to the left of k minus 1 is already sorted. So we're going to save the value we're trying to put into the leftmost sorted part of the array as the very end of the reign. K is the first element past the sorted left side of the array, so this is the next one we need to put in place on the left-hand side. Inside the outer loop, we have to find out where we're going to put this value, moving stuff out of the way as we go. We start i at k minus 1, so now we start i at the rightmost part of the piece of the array that's already been sorted, and then we have a while loop that says, while we haven't run past to the leftmost part of the array because our value that we're inserting could be smaller than anything on the left, so we have to make sure we don't go past that piece, and also while the value we're trying to insert is less than the current element we're looking at. That means, we haven't found the right place for a value yet because this element is bigger than value. Inside the body of the while loop, we copy whatever is in array i, the location we're currently looking at onto array i plus 1, so we're copying that over to the right, and we decrement i. So we keep moving to the left looking where we should put value. This isn't a swap, this is just a copy. Then when we're done, when we've finally found the insertion point, we set array i plus 1 equal to value, to put the value into the insertion point. You might wonder why this is i plus 1 and you could use a pencil and paper to see it or watch how it works, but if in fact we get all the way to i equals 0, and value is still less than array zero, we're copying array zero into array one, but then we're making i negative one. So after we're done with that while loop, we need to add one back into i to get to the correct place to put value. For our algorithm analysis, this outer loop goes from one up to n minus 1, so that's n minus 1 times. In the worst case, in this inner loop, we might have k equal to n minus 1, so we set i equal to n minus 2, but if in fact value is smaller than everything to the left, then this while loop because it goes while i is greater than or equal to zero, this while loop would execute in that worst-case n minus 1 times. So again, even though this inner loop is a while loop, we still need to multiply this complexity by the outer loop complexity, and we've seen before that n minus 1 times n minus 1 is n squared minus 2n plus 1, and when we throw away the lower order terms, this is also n-order n-squared sorting algorithm. Let's go take a look at a visualization for insertion sort. For our visualization, we will search on Insertion Sort visualization, and here's one down here that's 18 seconds long, so this is going to go very fast. You can see that the leftmost part, see this is the unsorted part, and we're finding the place to put the element on the leftmost part of the unsorted part, and then putting it in. We're shifting everything along as we go to get there, and that was insertion sort. To recap, in this lecture we learned how insertion sort works, and we discovered through our algorithm analysis that this is also an order n-squared algorithm. In case you're getting dismayed and think that the only way we can sort an array of values is within order n-squared algorithm, we can actually do it faster than that, but we have to learn an important idea first. So we'll get there, but we're not there yet.
