- [Instructor] Insertion sort.
Well, we've already seen bubble sort and selection sort.
Now we're going to take a look
at another algorithm, insertion sort.
Insertion sort works much the way
you might sort cards in your hand, when playing a card game.
Imagine holding the cards in your hand, fanning them out,
and treating the leftmost card as sorted.
Then, starting with the next card to the right,
you extract the card from your hand
and insert it into the correct place,
with respect to what's already been sorted.
That's insertion sort.
Insertion sort is a stable algorithm
and it tends to be a little faster than bubble sort
or selection sort.
Why is that?
It's because on each pass
it ignores all but one unsorted element.
And we're gonna have to look more closely
to see why that works.
Here's some pseudo-code.
Notice that we start with this index i equals one,
because we're treating the zeroth element as already sorted.
And then, similar to bubble sort and selection sort
there is an outer loop and an inner loop.
The outer loop iterates through all elements in the vector.
And for each element in the vector,
we find a value of the value that's at index i.
Think of that as taking the card out of your hand.
And then for all the cards that are to the left,
see this is j equals i minus one,
where j is the index of the inner loop,
while j is greater than or equal to zero.
And the value of v j is greater than the value of the card
that you're holding out, we shift those cards to the right.
This is the part that shifts the cards to the right.
And then we move to the left to look at the next value.
That's our while loop.
So our while loop keeps shifting cards to the right
or values to the right in our vector,
until we find a suitable place to insert the element
that we want to put into its correct position.
This pseudo-code here is saying
this is where we insert the value.
We've gone to the appropriate place
and we've found a spot for it.
And this iterates through all of the elements in our vector,
and then we're done.
So let's make this a little more concrete.
We'll use this example of cards.
Here we have a vector of cards.
We treat the leftmost card, in this case the eight,
as already sorted.
And we begin our sorting with the next card to the right,
that's the three.
Hence our pseudo-code begins with an index one
and not i equals zero.
So we extract that card.
We take it out of the vector.
And then we're going to shift all of the elements
that are to the left of that card, to the right,
until we find a good place to put that card.
In this case it's simple.
We only have to shift the eight one position.
This is the part that does the shifting,
as shown in the pseudo-code earlier.
And now you can see exactly where that three's gonna go,
it's gonna go to the left of the eight.
And we insert it back into the vector
in the appropriate position.
That's insertion sort.
In the next iteration we'd pull the six out.
We'd shift the eight over.
We'd put the six in the correct place.
We wouldn't need to shift the three,
that would not be putting it in the correct place.
And we just iterate through the whole vector that way.
Notice that when we found a spot for the three,
we didn't have to look at any of these other positions.
We just completely ignored this part of the vector.
Let's take a look on VisuAlgo.
The values that are already sorted
are marked in that yellow or orange color.
We pull the value out.
We shift values over to the right
until we find an appropriate place to insert our value.
And then we insert it.
All those light blue elements,
we're not even looking at those.
Just completely ignore those.
We only work within the portion of the vector
that's already sorted.
So now we have a sorted list.
Let's ask ourselves, is insertion sort stable?
Yes.
Insertion sort guarantees
that if duplicate values appear in the vector,
that their relative positions
will be preserved after sorting.
Now why is that?
Let's go back to this example of the cards.
And here's a vector of cards where we have duplicate values.
Notice that we have two sixes,
the six of clubs and the six of hearts.
Notice also their relative positions.
The six of clubs is on the left
and the six of hearts is on the right.
And we're gonna show that that relative position
is preserved during sorting.
So that was our start vector.
After three iterations our vector will look like this,
with six in the correct position.
After five iterations,
we have all of these elements correctly sorted.
And now we're ready to find a place for that other six.
So let's watch in detail what happens in that iteration.
We pull the six out of the vector.
You can see that we're going to shift the 10, the nine
and the eight over one to the right,
to make a space for the six.
And then we're going to insert the six
into the correct position.
So we see that the relative positions
of the two sixes is preserved.
The six of clubs is still on the left
and the six of hearts is still on the right.
So we know that insertion sort is stable.
Now what about its complexity?
Consider the worst case,
where the input is sorted in reverse order.
It's not uncommon that the worst case scenario
is with the input in the exactly the opposite order
that you want it to be in.
To put the last element into the correct position
we need to perform n minus one comparison
and n minus one swaps.
For the next element we need to perform
n minus two comparisons and n minus two swaps, and so on.
And so this gives us two times n minus one,
plus n minus two, plus n minus three, and so on,
down to one.
And if we solve that recurrence, we get n times n minus one.
And so we have a complexity of big O of n squared.
Here's a table showing a comparison
of the three algorithms we've looked at so far.
Bubble sort, selection sort and insertion sort.
As we've said, insertion sort is faster than bubble sort
and selection sort,
because it ignores the unsorted portion of the vector.
For the same reason, it can process data online.
What does that mean?
Well, we have online and offline algorithms.
An online algorithm is one that continues to take data
while it's working.
This means that while we're sorting,
we could continue to add new elements
to the unsorted portion of the vector,
and the insertion sort algorithm
would continue to work just fine.
If we did this with bubble sort or selection sort,
these algorithms would fail.
So one of the big differences between insertion sort
and these other two algorithms is that it can work online.
And despite the fact that all the algorithms
have O event squared complexity,
insertion sort typically outperforms bubble sort
and selection sort.
Why?
For the exact reason that I've already explained.
Insertion sort only scans the sorted portion of the vector
when finding the correct position for a given value.
It limits the scope of its work.
Furthermore, the closer an out of place element is
to its correct position,
the fewer steps we need to put it into the correct position.
And that's another feature of insertion sort
that makes it a little faster
than bubble sort and selection sort.
So in summary, insertion sort has
O event squared complexity.
It's stable.
It's generally faster than bubble sort and selection sort.
And in our next video, we're gonna code it up in C++.
We'll complete an implementation of insertion sort.
Also, we'll perform an experiment where we set timers
to time each of the three algorithms
as they sort random vectors.
It'll be interesting to see that result.
That's all for now.