>>Let's continue our study of sorting algorithms by examining insertion sort. Now here's the
algorithm for insertion sort. It's very similar to sorting cards as they're dealt. So one
at a time, what you do is you put the next card in sequence with respect to the previously
sorted cards. So we're inserting the next card into a sorted order, that's where the
name of the algorithm comes from. And as I mentioned before, it's very important that
you know not only the steps to the algorithm, but you match the name to those particular
steps because that's how we talk about them in computer science. It's also how I ask about
them on tests and so that's important. The challenge to this is the sequencing is tricky
to do efficiently. So if you tried to do this sort of by the seat of your pants you probably
wouldn't come up with a good algorithm. So you've got to use the algorithm that I'm presenting
here. That is, if you do something else on an examination it will be marked as wrong.
This is really important.
So, let's take a look at how this works in practice. Now just as in selection sort when
we were dividing data into things that had been previously sorted and things that haven't,
we're doing the same thing with insertion sort. So for example when your first card
is dealt in the hand, which in this case would be a five, that means we know exactly where
it is. It's in the right place and it's already sorted with respect to itself. Because how
could it not be? So the first thing we do is we take the second item, which is three
and we put it in a temporary location. I'm showing this over to the side. Now we compare
that temporary location to the value that's in the first position. We can see that five
is bigger or three is smaller, whichever way you want to think about it, so we move the
five over. Now notice at this point we do have five twice in the array. The three is
stored to the side so we're going to be able to move it back. Because we've hit the end
of the array, we can see that three has to go in first. So now three and five are sorted
with respect to each other and we're ready to start out second iteration.
So here's the second iteration. Now one is the value that we're trying to put in with
respect to the others, and so one gets moved to the temporary location. Now one is smaller
than five, so five gets moved over into ones position. One is also smaller than three.
So three gets moved over, and then at the end we move the value from temp into the first
position. Let's look at the third iteration now. Four gets moved into temp, five is bigger
than four so it gets moved over, but four is bigger than three so three does not get
moved over. Instead, four gets moved into the position that five was at first. And so
there we have four values sorted.
Here's the fourth iteration. The two gets moved into the temporary position. Two is
bigger than five, so five gets moved over. Two is bigger than four, so four gets moved
over. Two is bigger than three, so three gets moved over. Now two is bigger than one so
one does not get moved over. Instead, two gets moved into the position where three is.
So let's take a look at the last iteration.
Now we can see that six is bigger than five, but remember that's us looking ahead. We can't
do that; we have to be very systematic. So six gets moved to a temporary location. Now
six is bigger than five, so five doesn't get moved over and instead we recognize that six
is there-- that it belongs in its current position. So we've got an interesting boundary
condition we had to deal with in this particular case. So, let me show you a different way
to look at these four iterations. This is a little bit more abbreviated and this is
how I usually do it on a test. So we have different numbers here so you'll see a second
example. You can see we start with one. Well, one is smaller than three. So although we
move three over into temp, we don't have to move it back. Then we go to the iteration
with nine. Nine gets moved over to temp but it doesn't get moved back. Now with four,
four gets moved over to temp. Nine is bigger than four so it gets moved over, and then
four gets moved in. So it's the same layer of expressing these just without all the arrows
involved, and with a way that's a little bit easier to work on a test.
Our next iteration is putting two in the correct position. So two gets moved over to temp.
Now nine, four, and three are all going to move over one position because two is smaller
than those values, and then two gets moved back into position. Here are the last two
iterations. Six gets moved over to temp. Six is smaller than nine, so it gets moved over.
Five gets moved over to temp. Nine is bigger than five and six is bigger than five so they
get moved over. And lastly, five gets moved into position. When you look at this, this
gets all the data sorted. You may want to try a few examples the first way with the
arrows to make sure you really understand what's happening in the algorithm before you
do it this way. You do need to know how to trace the algorithm this way because this
is usually the way I usually ask it on examinations.
So now let's design our loops. The outer loop we noticed starts at index one, not at index
zero and progresses to the end of the array-- another perfect case for a for loop. The inner
loop starts at the index of the outer loop and moves to the beginning of the array, not
to the end of the array. Now notice the inner loop stops when the temp variable is larger
than the data, or it can stop when we reach the first array index. With all these different
conditions it's probably easier to use a while loop than a for loop, although it can be done
successfully either way. I'm going to show it with a while loop.
So here's the code. Notice our outer loop started at position one and went to eh end
of the array. Now what I'm doing here is moving the data to temp. So temp gets the value of
data of start, and our index gets the value of start. Now while the index is greater than
zero, so that's making sure we don't step off the beginning part of the array, and temp
is smaller than the data at the index, we move the data over. So that's the step that
we're seeing most of the time. Then we subtract one from the index. When we get to the end
of the loop, we move the temp value into data of index. So notice this code is not very
long, it's actually pretty short. Its just a little bit trickier to write is all. So
you might be wondering now why we should study sorting algorithms at all.
I told you before how interesting the story of sorting is, but let's think about what
we're really learning here. Well first off, this is one of our first exposures to why
algorithms matter. We have seen it in another place with linear search versus binary search,
but this is reinforcing the idea that how you do things as very important. Since algorithms
are essential to computer science, this really gives you a taste of what my discipline is
like. Once more sorting algorithms are the foundation for many other algorithms. So you'll
often here people say: "Hey we could do something like selection sort or we could do something
like insertions sort." If you don't know what those algorithms are you can't really participate
or understand that discussion. It's also a really good place to practice theoretical
tools. Now we don't have these theoretical tools yet, but you do see the need for them.
Because the minute you have two different ways to do things, you have to think about
which way is the better way. Now special circumstances may impact general rules. For example-- partially
sorted data. I worked out a partially sorted data example in much greater detail for you
to enjoy on Janux. So keep programming!