Insertion Sort Algorithm

Computer science

Introduction to Programs Data Types and Variables
Binary Numbers
Python Lists
For Loops in Python
While Loops in Python
Fun with Strings
Writing a Simple Factorial Program. (Python 2)
Stepping Through the Factorial Program
Flowchart for the Factorial Program
Python 3 Not Backwards Compatible with Python 2
Defining a Factorial Function
Diagramming What Happens with a Function Call
Recursive Factorial Function
Comparing Iterative and Recursive Factorial Functions
Exercise - Write a Fibonacci Function
Iterative Fibonacci Function Example
Stepping Through Iterative Fibonacci Function
Recursive Fibonacci Example
Stepping Through Recursive Fibonacci Function
Exercise - Write a Sorting Function
Insertion Sort Algorithm
Insertion Sort in Python
Stepping Through Insertion Sort Function
Simpler Insertion Sort Function

Insertion Sort Algorithm Visual description of the insertion sort algorithm

Back

Insertion Sort Algorithm

⇐ Use this menu to view and help create subtitles for this video in many different languages. You'll probably want to hide YouTube's captions if using these subtitles.

What I wanna 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 wanna make it clear,
it is not the most efficient way to sort a list.
But let's just—
I think it's a good starting point
where we're getting warmed up for sorting lists.
It's called "Insertion Sort".
I'm gonna give a graphical description
of the algorithm for insertion sort.
And just 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 can be a specific implementation of an algorithm.
Once I have a general algorithm,
I can implement it in Python,
I can implement it in C,
I can implement it in Java.
Those are all specific programs,
but they'd all be implementing
the same way of doing the sort.
And that's what I'm just describing—
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,
'cause 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].
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 1st 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 0th element over here,
but when you look at—
when you start with the 0th element,
you'll like "Hey wait, there is nothing before to compare it to,"
so it really doesn't make sense to start with 0th element.
So, really, if you were to implement this algorithm,
you'd start with the [1st] element—
Oh, sorry! You start with—
If this is the 0th element,
you start with the 1st element right over here.
This is 0th, this is 1st, I know this,
you'll confusing when you referred this is the 1st element
but this one is the 0th.
So you start with this 3 here
and 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 wanna do is you wanna shift—
you wanna shift 7 where the 3 is.
So let me put it out here—
so we're using—
we're trying to compare 3 to everything before it, right now.
we're trying to compare 3 to everything before it.
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 nothing lower—
there's no elements before the 0th 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,6]
And one thing you'll find interests—
there're something to pay attention to—
as we build this list, so we—
the 0th element is now defintely less than the 1st element
and everything up to and including the 1st element
is now sorted.
everything up to and including the 1st element
is now sorted.
And that will be true as we keep going through this—
as we keep going through higher and higher indices,
up to including that index
after we've done that pass will be sorted.
And I'll try to point it out as we go along.
So, we did the first index,
now we can move on to the 2nd 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 was.
And then you could either just keep comparing,
or you could just stick the 1 where the 7 is.
And then you 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—
our list now is going to be [1,3,7,2,4,6]
So notice, after we've gotten to the nth index—
so in this case this is the index 2
where that 1 was right over there—
everything up to and including that index is sorted.
This part right here is sorted.
It's going to be—
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.
That is the 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 [looking]—going to the left.
And so now after this pass—
in this pass we're 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].
I notice, everything up to and including the 3rd item—
the 0th, 1, 2, 3rd item—
is now sorted.
And now we are ready to look at this—
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.
You don't always have to—
so in this example, we said:
'Hey, 2 is less than 7?'
The 7 replaces where the 2 is
which you should do.
And then we had the 2 replaced where the 7 is.
But the reality is,
you can keep going down
until you find a good place to fit the 2,
and shifting everything to the right as you do it,
and then put the 2 in.
Although this way is a little bit easier to keep track of.
And wow, 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'll stop, we're done.
Now, everything up to and including the 4th item
in this list—01234—
is now sorted.
And now our list looks like—
let me scroll down a little bit—
Now, our list looks like this—
You write it down—
It is [1,2,3,4,7,6].
And now we can go to this last element in the list—
This is the 6 we're now comparing—
And it's the last time we'll did this
where was 4 that we were care about.
But now we're care about 6.
'Is 6 less than 7?' 'Sure, it is.'
So let's put the 7 where the 6 is,
and let's put the 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 gonna 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,7]
In the next video,
I'm actually going to try to implement
this algorithm that I just described.
And I'm gonna implement it in a simple Python function.

Questions
Tips & Feedback

Be specific, and indicate a time in the video:

At 5:31, how is the moon large enough to block the sun? Isn't the sun way larger?

Have something that's not a question about this content?

Post a tip or feedback
General discussion about the site
Report a technical problem with the site
Request a video or feature

This discussion area is not meant for answering homework questions.

Formatting tips

Cancel or

( total)

Share a tip

When naming a variable, it is okay to use most letters, but some are reserved, like 'e', which represents the value 2.7831...

Suggest a fix

At 2:33, Sal says "double bonds" but should say "single bonds."

Have something that's not a tip or feedback about this content?

Ask a question
General discussion about the site
Report a technical problem with the site
Request a video or feature

This discussion area is not meant for answering homework questions.

Formatting tips

Cancel or

Discuss the site

For general discussions about Khan Academy, visit our Reddit discussion page.

Flag inappropriate posts

Here are posts to avoid making. If you do encounter them, flag them for attention from our Guardians.

abuse

disrespectful or offensive
an advertisement

not helpful

low quality
not about the video topic
soliciting votes or seeking badges
a homework question
a duplicate answer
repeatedly making the same post

wrong category

a tip or feedback in Questions
a question in Tips & Feedback
an answer that should be its own question

about the site

a question about Khan Academy
(Visit our FAQ)
a post about badges
a technical problem with the site
(Report a problem)
a request for videos or features