Four Semesters of Computer Science in 5 Hours Insertion Sort

[00:00:00]
>> [MUSIC]

[00:00:03]
>> Brian Holt: So let's talk about Insertion Sort. Something that you actually will use. Insertion Sort is, really great for arrays that you are pretty sure, are already sorted or very close to sorted. Where it falls apart is if the array is not sorted at all. It is a step more complex, but I still think it models human thinking fairly well.

[00:00:29]
>> Brian Holt: And yeah, occasionally useful. It's worst case, it's pretty similar to bubble sort, which I would think would be a totally randomly sorted array. But again, it is useful for almost sorted arrays. So you can see here, its just kind of, you have your sort of part of the array and you kind of start trying to grow that, and that's kind of how assertion or insertion sort works.

[00:00:53] So we're gonna start at the beginning of the list. And assume you have a sorted list of length 1. So let's do this, New Link Page. Okay, where's my pen?
>> Brian Holt: Well, I guess that's what it is.
>> Brian Holt: Okay, so,
>> Brian Holt: Here we go, draw. Okay, so say we have an array of

[00:01:45]
>> Brian Holt: Like 5, 3, 6, right?
>> Brian Holt: Okay? So the first thing we're gonna do is that, we we're gonna kind of, start thinking this in terms of like a sub array. We're not actually gonna separate that out into a separate array but, we're gonna kind of, start visualizing this is as a sub array.

[00:02:08] A sub array is going to start at the first element, at first it's only going to be the first element, right? So, our sub array is basically, 5, right? And now, we have a list of one within our list, right? Another thing I'm going to use the word list interchangeably, and I think that's, yeah.

[00:02:25] It's array in JavaScript terminology, but if you come in from like Python it's called a list whatever. Okay. So we have a sort of list of one, 5. You can't sort 5 any more than it is, 5 is automatically is sort of because it's length one, it's automatically sorted, right?

[00:02:41] So and then we're gonna start grabbing things from the unsorted part of the list, and inserting that into the sorted part, right? So the first thing we're gonna do, is we're gonna come here and grab 3. And then, we're going to loop over backwards and say, okay, where do you go?

[00:02:58] So in this particular case, we're gonna say, k is 3 greater than 5? No. So it's going to go to the next place, k is 3 less than 5? Yes. So what we're gonna do here is, we're going to put that in here, and insert at the beginning of the array,

[00:03:18]
>> Brian Holt: And at that point, you can ask, okay, you would ask is 3 greater than 5? Yes, okay, then you just leave it where it is right? So that's kind of the idea with insertions sort, is your just gonna grab these numbers, and you're going to loop over the rest of your array, and then insert them into the correct place.

[00:03:32] Hence, insertion sort.
>> Brian Holt: Let's see, make sure I talked about everything I meant to.
>> Brian Holt: Again, you just keep growing the size of your sorted part of your array by inserting new numbers into that. So let's talk about how you actually implement that, right? So, you're gonna have two loops, right?

[00:03:59] You're gonna have an inner loop and an outer loop, so this ends up being again n squared. But when you're comparing it to bubble sort, it actually ends up having much more favorable coefficients particularly when it's sorted, right? And that ends up being really useful to us