What I want to do in this video is
go over what I think is one of the more intuitive ways
to sort a list.
It's how I would probably sort it, if I had to do it manually.
But I want to make it clear, it is not the most efficient way
to sort a list.
I think it's a good starting point to getting warmed up
with sorting lists.
It's called insertion_sort.
And I'm going to give a graphical description
of the algorithm for insertion_sort.
And just so you know what, algorithm
sounds like a very fancy word, but an algorithm
is really just a way of sorting it, or a process for doing it,
or a method for doing it.
A program is a specific implementation of an algorithm,
or it can be a specific implementation of an algorithm.
Once I have a general algorithm, I could implement it in Python.
I could implement it in C. I could implement it in Java.
Those are specific programs.
But they'd all be implementing the same way of doing the sort.
And that's what I'm describing here,
the insertion_sort algorithm.
So let's just start with a simple example.
Let's say that I have a list.
Let's say I have a Python list, because we're
going to be working in Python for this.
And that list is, let's say, it is 7, 3, 1, 2, 4, 6.
And so the way that we do insertion_sort
is you go element by element.
And then you compare it to the elements before it.
And then you look for the first element before it
that it is actually less than.
And then you just stick it right over there.
So let me show you what I'm talking about.
So you could start with the 7, the 0-th element over here.
But when you start with a 0-th element,
you're like, hey, wait, there's nothing
before it to compare it to.
So it really doesn't make sense to start with the 0-th element.
So really, if you were to implement this algorithm,
you'll start it with the third element.
Or sorry, you'll start it with-- if this is the 0-th element,
you'd start it with the first element right over here.
If this is 0-th, this is first.
I know this can be a little confusing when
you refer to this as the first element.
But this one's the 0-th.
So you start with this 3 here.
And then you start comparing it to all of the elements
before it.
And as soon as you find an element that 3 is less than,
you stick it in that part of the list.
So what you do is you say, OK, is 3 less than 7?
Well, yeah, it is less than 7.
So what you want to do is you want to shift 7 where the 3 is.
So let me put it out here.
So we're trying to compare 3 to everything before it right now.
So you say, OK, is 3 less than 7?
Yeah, it is less than 7.
So let's put the 7 where the 3 is.
And let's put the 3 where the 7 is, especially
because there's nothing left to compare the 3 to.
There's no elements before the 0-th element,
so let's just stick the 3 right over there.
And so our list now looks like this.
Our list now looks like 3, 7, 1, 2, 4, and 6.
And one thing you'll find interesting,
or something to pay attention to,
is as we build this list-- so the 0-th element is now
definitely less than the first element.
And everything up to and including the first element
is now sorted.
And that will be true, as we keep going through this.
As we keep going through higher and higher indexes, up to
and including that index after we've done
that pass will be sorted.
And I'll try to point that out as we go along.
So we did the first index.
So we already did the first index.
Now we can move on to the second element,
which is this 1 over here.
And so you take that 1.
I'll put it on the side right over here.
You take that 1 and you compare it to each of the elements
before it.
OK, is 1 less than 7?
Sure, 1 is less than 7.
So let's stick the 7 where the 1 is.
And then you could just keep comparing,
or you could just stick the 1 where the 7 is.
And then you would say, OK, is 1 less than 3?
Well, yeah, sure.
It's less than 3.
So let's stick the 3 where the 1 is.
And let's put the 1 where the 3 is.
So what is our list now?
Our list now is going to look like 1, 1, 3, 7, 2, 4, 6.
So notice, after we've gotten to the n-th index-- so
in this case, this was the index of 2
where that 1 was right over there-- everything up
to and including that index is sorted.
This part right here is sorted.
Other things are going to be thrown in here, probably,
as we go on.
But so far, this part is sorted.
So you can see by the time we get to the end of this list,
everything is going to be sorted.
So let's now go to the next index,
or the next item in the list.
And that is this 2 over here.
And so we compare the 2 to the 7.
2 is definitely less than the 7, so let's put
the 7 where the 2 is, and let's put the 2 where the 7 is.
Now you compare the 2 to the 3.
2 is less than 3.
So let's put the 3 where the 2 is, and let's
put the 2 where the 3 is.
Then compare 2 to 1.
Is 2 less than 1?
No, it is not less than 1, so we don't have to do anything else.
We don't have to keep going to the left.
And so now, after this pass-- in this pass,
we were comparing this 2 item to everything before that.
So after this pass, our list looks like this.
Our list looks like 1, 2, 3, 7, 4, 6.
And notice everything up to and including the third item,
so 0-th 1 2, third item, is now sorted.
And now we're ready to look at the next element in the list.
And one thing I want to make clear,
when you actually implement it, there's
a couple of ways to do it.
So in this example, we said, hey, 2 is less than 7.
We had the 7 replace where the 2 is, which you should do.
And then we had the 2 replace where the 7 is.
But the reality is you can keep going down,
until you find a good place to put the 2,
and shifting everything to the right as you do it,
and then putting the 2 in.
Although this way, it's a little bit easier to keep track of.
And well, maybe we'll explore different ways
to do it when we actually implement the algorithm.
Anyway, let's look at this 4.
Same exact idea.
4 is less than 7, so let's put the 7
where the 4 is and put the 4 where the 7 is.
Is 4 less than 3?
No, it's not less than 3, so we stop.
We're done.
Now everything up to and including the fourth item
in this list, 0, 1, 2, 3, 4, is now sorted.
And now our list looks like-- let
me scroll down a little bit-- now our list looks like this.
Let me write it down.
It is 1, 2, 3, 4, 7, and then 6.
And now we can go to this last element in the list.
This is the 6 that we're now comparing.
Actually, the last time we did this,
it was a 4 that we cared about.
But now we care about the 6.
Is 6 less than 7?
Sure, it is.
So let's put 7 where the 6 is.
Let's put a 6 where the 7 is.
Is 6 less than 4?
No, it's not.
And so we stop, because we know that this
is going to be sorted.
If we went any further, we're just
going to get elements that are less than or equal to 4.
So we are done.
We have sorted this list.
The sorted list is now 1, 2, 3, 4, 6, and 7.
In the next video, I'm actually going
to try to implement this algorithm that I just
described.
And I'm going to implement it in a simple Python function.