[MUSIC PLAYING]
DOUG LLOYD: So in this
video, we're going
to take a look at insertion sort,
which is another algorithm that you
can use to sort an array.
And in this example, we're going
to use an array of integers.
An algorithm, recall,
is a step by step set
of instructions for completing a task.
The idea with insertion
sort is as follows,
we're going to build the sorted array
in place, shifting elements that
were previously considered
sorted, if we need to,
in order to fit those
elements in the right position
in the sorted portion of the array.
This is fundamentally different
than how we've done things
with selection sort or bubble sort.
Recall with those
algorithms what we do is,
we usually end up just
sorting one element.
We have to go through
the entire array to put
one element in the correct position.
For bubble sort, it's usually the
largest element that's available.
For selection sort, it's
usually the smallest element.
But we're only getting one at a time.
We're not making-- you know, we have to
go through this array multiple times.
With insertion sort, we only are going
to move forward through the array once.
We might have to look back at things
we've already sorted to sort of shift
them around to make room.
But we only have to make one
forward pass of the entire array.
So that's sort of a
fundamental difference.
And the way we do this is
we get started, we just
say the first thing we see is sorted.
It's the only thing we've seen so far.
So it might as well be sorted.
Then we just do the following
for every element that remains.
We look at that element
and we maybe shift things
that we previously
considered sorted, just
to make room for it, until we
get through every single element.
This will probably make a little bit
more sense when you see it visually.
So let's illustrate that
now with this array.
In this array, what I want to do is
everything that's red is unsorted,
everything that's blue is sorted.
So keep that in mind as we
go through this example.
So recall that the
first thing we do is we
declare the first element
of the array is sorted.
So that's five.
We just see it.
We're like, got it.
This one is sorted.
So we have the sorted portion in blue.
And we this five element
unsorted portion in red.
Now we're going to repeat
the following process
until everything else is sorted.
We look at the next unsorted
element and we maybe
shift things around in
the blue section in order
to put that element in the
correct sorted position.
So the first element that we see is two.
We take a look, we see
is there anything we need
to do to put two in the right spot.
The answer is yes.
We need to shift five over in
order to put two in front of it.
So we slide five over.
And then we put two where
five basically was in memory.
And now two, five is sorted and
the red portion is unsorted.
Let's repeat this process again.
The next thing we see is a one.
We take a look at the blue portion.
What do we have to move?
Well here, again, we
have to move everything,
because one comes before
both two and five.
So both of them slide over.
And that leaves one
vacancy to put the one.
The next thing we see is three.
What do we have to move this time in
order to get everything into position?
Well, it's not everything this time.
We just have to move the five over.
So we move the five to
where the three was.
And then we put the three
where the five just vacated.
The next element that we see is 6.
And this is sort of a special
case of insertion sort, where
it's larger than everything
in the sorted portion, which
is great because then we don't
have to move anything at all.
We just say, all right, well,
six is in the right spot.
We can just declare six to be sorted.
And then the final element
we have here is four.
So we take a look at that.
We look back at the blue portion,
the sorted portion of the array.
We figure out what we
need to slide over.
It's just the five and the six.
They slide over which
makes room for the four.
And now we have sorted our entire six
element array using the insertion sort
algorithm.
Now again, this feels very different
than anything we've seen before.
But unfortunately it's
still n squared algorithm.
So for example, imagine if
the array is in reverse order.
So it's six, five,
four, three, two, one.
In that case, we have to shift each of
the elements n positions every time we
want to make an insertion.
So we see this six, five,
four, three, two, one array.
The six is good.
Then we see the five.
We have to shift the six over.
Then we see the four.
We have to shift of
six and the five over.
Then we see the three.
We have to shift the six
and the five and the four.
So we just keep getting worse.
We have to keep making all these shifts.
And each one of those costs us.
So even though this looks
and feels very different
than a bubble sort or a selection sort,
this is still n squared, unfortunately.
In the best case scenario though,
the array is perfectly sorted.
And this is sort of that example we saw
a second ago with the five and the six,
where we just said, oh, well
that's kind of convenient.
The six is greater than
everything in the sorted portion,
so we just kind of moved the line over.
We just changed it from red to
blue without changing anything.
In the best case scenario, we just
do that for every element-- one, two,
three, four.
We just keep changing them
red to blue, no shifts.
And so if we think about this
in asymptotic notation, that
means that this algorithm is a big O of
n squared, but it's still omega of n.
I'm Doug Lloyd.
This is CS50.
