This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Exercise 3: Insertion Sort" Lesson
[00:00:00]
>> [MUSIC]
[00:00:03]
>> Brian Holt: So, you have the outer loop that goes over the whole disk, right?r And the index signifies, right? So, if you have outer for loop that has index I. I represents where you're sort of list is, right? So if your index is at one you assume that you have everything after one is on sort everything before one is sorted, right?
[00:00:23] And then as I goes to two everything before two is sorted everything after is on sort of, right? That's what the outer loop signifies with that index, right? Then you're going to have your inner loop which is going to go over just the sorted part of the array and it's going to insert whatever the item is after that part.
[00:00:42] So let's just draw that out so you can kind of see what it looks like.
>> Brian Holt: Let's just do like a new tab. That's better, have actual canvas to draw on. [COUGH] All right so coming back here to I have. We'll just do like 4, 1, 0, right?
[00:01:14] So, at first my eye is going to be pointing at this one, right? And so everything after that's unsorted, right? And then your j, which is going to be your inner index, right? So j is going to be asking everything after I, so in this particular case, sorry, the first element after I which is going to be one here, right?
[00:01:38] Where does that actually go in the array so it's gonna ask does it go at index 1? No, does it go at index 0? Yes, right? And the same thing with 0. So i at this point is going to point here.
>> Brian Holt: Right? And so you gonna ask the first element after i, which is going to be 0, right?
[00:02:00] And then, j is going to ask k does it go after well, at this point it's going to be 1, 4, right? So it's going to ask does it go after 4? No, does it go after 1? No, does it go after 0? No, sorry, yes. [LAUGH] So at that point you're gonna say 0, 1, 4, right?
[00:02:22]
>> Brian Holt: So that's the basic gist behind it, right? See, the nice thing about insertion sort is that inner loop only does parts of the area at a time and only the parts that it needs to do, right? Whereas with bubble sort we're doing the entire array with both loops every single time.
[00:02:35] And that's why bubble sort is not necessarily great.