Insertion sort in python Basic implementation of insertion sort algorithm
Insertion sort in python
- What I'm going to do in this video is
- attempt to create an implementation
- of the insertion sort algorithm
- that we talked about in the last video.
- I'll do it as a Python function.
- So I'll call the Python function insertion_sort()
- and it will take in a list—
- so list is its parameter in the function definition—
- so we'll have to pass in a list as an argument.
- And let's—what we're going to do is
- we're going to step through each of the slots in the list.
- I guess we could call it that way.
- So let's say "for index in range()".
- We could start at the leftmost slot in the list.
- So, we could just say "len()"—
- "len" just means—it's short for "length"—
- so length of the list.
- So what this would do (is)
- this would start index—
- so let's say the list has four elements in it—
- then "len(list)", this right here,
- would be 4, would evaluate to 4.
- "range(4)" would produce a list
- that has elements [0,1,2,3] in it.
- And so, index would be able to step through
- the different indices for this list right over here.
- And we could do it that way,
- but you might remember from the previous video
- that when you're doing the insertion sort
- it doesn't actually make sense
- to start at the very leftmost element.
- Because there's nothing to compare it to the left.
- So we can actually just start
- at the second to the leftmost element.
- And the leftmost element is the 0th item,
- so we can start at the first item.
- So now, if the list has a length of 4,
- this right here will produce [1,2,3].
- So, 1 would be the second to the leftmost element.
- 2 would be the next one to the right.
- 3 would be the last one.
- Remember, we always start our indices at 0—
- the 0th term is the leftmost element in a list.
- So fine, we can step through that.
- Let's get the value of—at that point in time—
- of the element that is at that index.
- So, that way we don't have to keep finding it,
- value is equal to list[index].
- And this by no means is going to be
- the most efficient implementation
- of even insertion sort.
- This is going to be my best try,
- writing it in real time,
- and in a way that hopefully...
- you might be able to understand it.
- So "value" is just the item in the list
- at each of those indexes
- that we're now going to compare to
- all of the items to the left of it.
- And what I want to do is—
- compare a value—I want to compare a value
- to each item to the left of it.
- So let's define a variable "i"
- and let's let this be the index of the things
- that I want to compare value to.
- And right from the get-go
- I want to compare value to the thing that is left of it.
- So "i" should have
- one lower of an index than "index".
- So "index - 1".
- So this is the index of the item
- that is directly left to it.
- But we're going to keep taking "i" lower and lower.
- So we can keep comparing value
- to things further and further to the left.
- And so what we want to do is we're going to—
- we want to keep comparing further and further left
- until "i" has gotten all the way to the beginning of the list.
- And "i" has gotten all the way to the beginning of the list
- when it is equal to 0.
- So what we want to do is,
- we want to perform this
- while "i" is greater than or equal to 0.
- Because if we keep taking "i" lower and lower and lower,
- we're going further and further
- to the left of the list.
- We don't want to try to perform it
- when "i" is—you know—further—is a negative number—
- that'll just start doing crazy things.
- So while “i” is greater than or equal to 0—
- what I'm going to do is
- I'm going to keep pushing "i" further and further to the left.
- So let's try it this way, so the first thing I want to do—
- we've already pushed it to the left once.
- So let's compare—
- so if "value" is less than the—
- this thing keeps syntax error
- because (of) waiting for me to keep typing—
- if "value" is less than the item that is now at index "i".
- So the item at index "i"—list[i]—
- the item at index "i" is this right here.
- So if it is less than that,
- let's shift the item that's over here—
- let's shift it one to the right.
- So the right slot is "i + 1"
- and I can't just say it's "index",
- because remember I'm going to keep pulling "i"
- lower and lower and lower.
- Because right now "i" is "index - 1"
- in the first pass through this while loop,
- but I'm going to—as you'll see in a second—
- I'm going to keep lowering "i",
- so it always won't be one left of "index".
- So I'm going to say, wherever "i" is,
- let's take the spot one to the right of "i"—
- one to the spot of—one to the right of that—
- so that's "i + 1" is its index.
- And let's replace that with whatever is at list[i],
- whatever is at "i", at slot "i".
- So we've essentially taken this thing right over here
- whatever number was there.
- And we're putting it in the slot
- that is one to the right of it. And then,
- and actually the way we were setting up that algorithm.
- Whatever's there is going to be...
- Well...I won't talk about that.
- We'll step through it and see how it all plays out.
- And then we can shift "value" to the left.
- So whatever was in this slot right over here
- will be replaced by "value".
- So list[i] will equal "value".
- So one way to think about it
- --Let me write a comment here--
- shift what was...
- shift number in slot "i" to slot "i + 1"
- or actually bucket "i + 1"
- --I guess is one way to think about it--
- And then you could say,
- shift number right—let me call it this way—
- shift number right—in slot
- --we're going to write this way--
- shift number in slot "i" right to slot "i + 1"
- And then over here, we are shifting...
- shift value left into slot "i".
- And so if you remember what we did in the last video,
- it's exactly describing it.
- We're comparing "value" to the thing to the left of it.
- If it's less than it,
- then whatever number was in that box/slot to the left of it,
- shift it to the right, and then shift "value" to the left.
- And now let's compare value
- to something one lower than that.
- So we want to decrement "i", we want to lower "i"—
- decrement is just increment down.
- So "i" is equal to "i - 1",
- and then we'll perform the loop over again.
- And now "value" will be compared—
- now "i" is two to the left of "index"
- --compared to that--
- if it is less than it, shift that to the right
- and shift "value" again to the left
- Now what if we have the situation
- where "value" is not less than
- the item that you are comparing it to?
- Well if it's not less than the item you're comparing it to,
- that means "value" is already going to be in the right place.
- It also means that you're done,
- and that you don't need to shift "value" any more to the left.
- And you don't have to shift the stuff to the left
- any more to the right.
- So then, we are done,
- and I <i>think</i> this could work
- unless I made some silly mistakes.
- So let's try to see if I could get this—
- if this actually works as a sorting algorithm.
- Let me save it, insertion_sort,
- and let me run it.
- Alright, so I didn't have any, at least, syntax mistakes.
- Syntax just means the actual characters I used—
- I didn't forget to put a colon here or greater than sign—
- it was actually able to process this,
- interpret this right over here.
- But let's see if it actually works.
- So let me define "a" list.
- Let's say [7,1,3,5,9,2]
- and let me put another 3 in there.
- So that is "a",
- Then let me see—this is the moment of truth.
- insertion_sort(a), let's see what happens.
- So remember, we're sorting it in place,
- this function doesn't return anything.
- But it should take whatever list that was,
- and had changed up all the elements
- so that now they are in order.
- So this is the moment of truth.
- Let's see what "a" looks like.
- There you go! It is sorted.
- So I don't think I made any major mistakes.
- So there you go.
- You have a version of insertion sort.
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?
This discussion area is not meant for answering homework questions.
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...
Thank the author
This is great, I finally understand quadratic functions!
Have something that's not a tip or thanks about this content?
This discussion area is not meant for answering homework questions.
At 2:33, Sal said "single bonds" but meant "covalent bonds."
For general discussions about Khan Academy, visit our Reddit discussion page.
Here are posts to avoid making. If you do encounter them, flag them for attention from our Guardians.
- disrespectful or offensive
- an advertisement
- low quality
- not about the video topic
- soliciting votes or seeking badges
- a homework question
- a duplicate answer
- repeatedly making the same post
- a tip or thanks in Questions
- a question in Tips & Thanks
- an answer that should be its own question