### 載入中...

相關課程

⇐ 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.

# Stepping Through Insertion Sort Function : Clarifying what "break" does and stepping through the insertion sort implementation

相關課程

選項
分享

0 / 750

- 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.
- Our final sorted list is: 1, 2, 2 and 3.

載入中...