Stepping through insertion sort function Clarifying what "break" does and stepping through the insertion sort implementation
Stepping through insertion sort function
- What I wanna do in this video is step trough the insertion sort function
- that we wrote in the last video.
- But before I do that I actually just want to focus on one part of it,
- cuz I realized that I used something that you probably don't reckognize
- cuz we haven't used it before.
- I used... I used the keyword right over here. I used BREAK
- and you might guess what BREAK means,
- but now I'll explain it explicitly.
- What BREAK means is: Break out of the smallest loop that you were doing
- so we were taking our item and we were kept comparing it to the thing to the left of it.
- We were taking value and kept comparing it to the left of it
- and as soon as we found value not beeing less than something to the left of it we said:
- Hei, we are done we don't have to keep going to the left
- and in that situation I wanna break the loop so we were breaking this WHILE loop
- and then we just continue in our next interation of this FOR loop over here.
- So that's what BREAK did.
- Now that out of the way let's actually step trough this program on a simple example.
- So let's say that someone calls... well let's just define...
- Let's just define a to be equal to... let me think about a fairly simple list...
- 2, 1... I don't konw... 2, 1, 3, 2.
- I think it's a good list over there and let's assume that we are calling insertion_sort...
- insertion_sort... insertion_sort on a.
- Let's think about what's going to happen.
- Well the first thing ofcourse that list... Let's keep track of all of the variables here
- so one of... so list is right from the get code going to refer to: 2, 1, 3, 2.
- That's list right from the get code and then we enter into the function.
- For index in range and let's parse this part right over here.
- So what is LEN of the list. So LEN of our list is the same thing as LEN of 2, 1, 3, 2
- and this is just really the number of elements. LEN is short for length. Not that much shorter,
- but LEN of this is just going to be one, two, three, four.
- It's going to be equal to 4 elements.
- So this right over here is going to be 4 and on the call RANGE between 1 and LEN of list is 4.
- This will return the list... this will return the list, starting at 1 and up to but not including 4.
- 1, 2, 3.
- And so these are the indices we want to use, because this...
- the first index is this right over here, second index is this right over here
- and the third index is that over here.
- Remember, this is the 0th index. So index is gonna keep incrementing between these two.
- It's gonna be 1 first, then 3, then 2.
- So let's just...
- Let me just create our variable index that's going to be whose scope is inside of the FOR loop.
- So let's say we have index.
- Index is going to start off beeing the first item.
- The first item in this list right here. The list is generated by range 1 coma LEN of list.
- So index is going to start off beeing 1
- and then over here we say value is equal to the index element in list.
- So let me define our variable value... value. So what is list of 1?
- What is the first element of the list? This is the 0th element, this is the 1st element
- so we are looking at this right over here.
- This is... It is the first element. So that's fair enough and then we define i to be index minus 1
- so let me put i over here and do a new colour.
- And now let's do i. It is index minus 1. Index is 1 so index minus 1 is 0.
- So it's the index of the item to the left of value. So that is going to be 0.
- This index is 1, this is 0
- and then we are saying WHILE i is greater than or equal to 0 do all of this bussiness over here
- and the first thing that we do over here is we compare value...
- we compare value to the object that is at the i'th element of the list.
- So let me write that over here. So list... list at i.
- So that is going to be the 0th element in the list. That is 2... That is 2.
- So we are comparing value. We are comparing 1.
- We are saying if 1 is less than the i'th element in list.
- If 1 is less than 2, then do this. Well 1 is definetly less than 2.
- We are essentially taking 1 and comparing it to the thing to the left and saying:
- Hei it's less than that so it's less than that.
- Let's shift this 2 to the right and let's shift 1 to the left
- and so we go into here and we say list i plus 1.
- So what's i plus 1?
- I plus 1 is 1. So this is list of 1. So this slot right over here.
- So this... in yellow that I just I don't know... so this slot over here.
- I is 0. I plus 1 is 1 so the i'th... the first item or the first slot is this slot right over here.
- Let's replace it whatever is at list.
- Whatever is in the i'th element or whatever is in the 0 slot as I guess I should call it.
- So let's replace it with this 2. Right, let me make it clear.
- In this time around this is 2 and this is the slot where the 1 was
- so we are going to put this.. we are going to replace that with 2
- and then in the place where the 2 was we are going to replace it with value
- and remember value was set to 1.
- So value is set to 1 and so our list now looks like 1, 2, 3, 2
- and hopefully this looks familiar if you remember when we first described the insertion_sort algorithm.
- So we go trough there and we don't... and then we... and now we want to decrement i.
- We say whatever i was. It's 1. We subtract 1. So now it's 0.
- So the new value for i is 0. The new value for i is 0.
- Actually... no, sorry. Whatever i was. I was 0. I was 0.
- You subtract 1 form that and now i is going to be negative 1.
- So now i is going to be... i is now going to be negative 1.
- And then we go to the WHILE loop and it says while i is greater than or equal to 0.
- Well i is now negative 1 so the WHILE loop no longer applies.
- This will return false. I is not greater than or equal to 0 so it won't perform any of this anymore.
- And so we'll now go to the next iteration of the FOR loop.
- And so now let's go to the... and essentially what's that signifying is that we are done with that element.
- We compared all the way to everything to the left of it and it found it's place
- or just found it's place in general.
- Now let's go to the first... next iteration of the FOR loop.
- Now index is going to be the next element.
- Now index instead of beeing 1 is going to be the next element
- in the list generated by this expression here.
- So index is now going to be 2... Index is now going to be 2
- and now list value is what's ever at the 2nd index so it's this item right over here.
- Notice. We were at the 2nd to the left now we are at the...
- we were at the first to the left or one right to the left of... it now or once base more to right.
- So value now is going to be 3. Value is now going to 3.
- I is going to be index minus 1.
- Index is 2. 2 minus 1 is... 2 minus 1 is 1. So this is...
- This is now 1. This is now 1 and we say; WHILE i is greater than or equal to 0.
- Well it's clearly greater than or zequal to... now greater than or equal to 0 now.
- Say if value is less than list the i'th element in list.
- So the value is 3 and is that less than... well what's at list i is no longer 2.
- So what in the first element. Well it actually still is 2. so it still is a 2.
- So if we look at the first element. The list... the first... the i'th element in list.
- I is 1. 0 1. It is still 2. So actually we didn't have to cross that out.
- It is still going to be.. it is still 2 right over there
- and so is... if 3 is less than 2 do this. Well 3 isn't less than 2 so you are going to do the else clause
- and you are just going to break out of this WHILE loop
- and that made sense because you said, hei look.
- We compared 3 immediately to the thing right before it to the left of it we say, hei
- 3 is in the right place. 3 is greater than 2. It is not less than 2
- so I'm not going to do all this shifting bussiness. I don't shift 2 to the right and 3 to the left
- and then look at the next item.
- I know that everything to the left of 3 is already sorted so 3 is not less than 2.
- It's definitely not going to be less anything to the left of it and so we are done.
- We leave it the way it is.
- And so then we break out and we go to the next iteration of the FOR loop.
- So now index is going to be the next item here. It is now going to be equal to 3.
- The next item in this list generated by this expression
- so it's now going to be 3. Index is now going to be 3.
- Value is now going to be... is now going to be 0, 1, 2, 3...
- Value is now going to be this item right over here.
- That is going to be value, cuz our index is now 3 so our value is now 2.
- Let me cross these guys out.
- Let me save some space.
- Value is now 2 and now... and now i is 2... i is... oh let me... i is index minus 1.
- So 3 minus 1 so that is 2.
- So i is now going to be 2
- and the object that is at list at the 2th element on the list, 0, 1, 2, is now going to be... is now going to be 3.
- And so the first thing we do while i is greater or equal to 0 while i is clearly greater or equal to 0.
- It's 2 right now.
- If value. If 2 is less than what the i'th...the i'th... what's in the i'th slot of list
- so 2 is less than 3 so we do perform this right over here
- and so what we do is whatever is at list of i plus 1 so list of i plus 1.
- I is 2. I plus 1 is 3. So whatever is at this slot, which is the 3rd slot where the 2 was.
- Replace it whith whatever is to the left of it.
- So we replace it with the 3.
- So we are going to replace this with the 3 and the next element...
- Take whatever was... that slot to the left where i is and replace it ...
- And replace it with... and replace it with the value.
- And replace it with value so then we replaced it with value so this thing is now going to be
- a 2 again and so... and then we... and now decrement i again.
- Now i is equal to 1 and we go to the WHILE loop again.
- I is clearly greater than or equal to 0. It is 1.
- Value is still 2. Remember 2 is what we are comparing
- and while we go trough this WHILE loop we are comparing to each of the items to the left.
- If 2 is less than whatever is at the i'th slot in the list.
- So the first slot in the list is 2.
- Well 2 is equal to that, but it is not less than that, so we don't have to do anything anymore.
- The thing is sorted. The 2s are in the right place.
- If it's equal to the thing to the left of it we don't have to shift anything
- and that means it is at least equal or greater than everything to the left of that
- since everything is sorted.
- Everything is sorted already.
- So then we are done.
- If... Since 2 is not less than 2 we BREAK out and we break out in the FOR loop it says...
- Okay let me see if there is anything left in this list to apply index to.
- There isn't. We have used everything in that list and so we break out of the FOR loop
- and we are done and the list should be sorted.
- We see right here, the list is sorted.
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