Insertion Sort

[00:00:00]
>> So, we just talked about bubble sort and I said bubble sorts, probably not one you're ever going to use. And the reason why you're probably never gonna use bubble sort and actually me rephrase, you'll never actually use bubble sort in any sort of real setting, it's strictly a teaching tool.

[00:00:19]
And that's because insertion sort is just strictly better. There's no situation that you're gonna find that bubble sort, outperforms selections or, sorry, Insertion Sort. There's another sort called selection sort that we're not doing today that is occasionally useful. But we're gonna go with insertion Sort because one, I think it's a bit easier to conceptualize, and two, I think it's more useful in general algorithm.

[00:00:45]
So insertion sort, again, works kinda in a way that the human brain maps sorting in its head. So you can see here in this little GIF, what is doing is it's starting at an array of length one, so zero right? And it's saying okay the very from array previous to index one is a sorted array, right?

[00:01:12]
So you have a basically a sub array of length one and an array of length one is always sorted, right? So if I have an array and it's just one number in there, that's a sorted array because you can't do anything else to that, it's just sorted because there's only one number in there, right?

[00:01:31]
So we're gonna take advantage of that concept and say, okay, what we're gonna do is we're gonna take the next number that this case, index 1, and we're going to insert that in a sorted way. So I have a list down here. We're basically gonna say everything before index 1 so basically just index 0 in this particular way is sorted, right.

[00:01:51]
So 3, this part of the array is sorted and this part of the array is unsorted. Then we're gonna take 2 here and we're going to insert that into the sorted place for it, right? So you're gonna say is 2 larger than 3? No. Move 3 to the right beginning of the list and insert 2 at index 0, right?

[00:02:13]
So basically we're just going to be shifting those numbers over as we iterate over it. Once we get to the beginning of the list, then we know that 2 was at the beginning of the list, okay? Now we're gonna take index 5 here, so we're gonna say, is index 5 larger than 3?

[00:02:31]
And then we're gonna say insert after 3, in which case, it is already after 3, so we don't have to do anything. So this just stays where it is, okay? Then we're gonna start at index 4 here. We're gonna say is index 4 larger than 5? No, move to the right.

[00:02:51]
So basically, 5 is going to end up here. And then we're gonna say is 4 larger than 3, is we're gonna say yes, so basically 4 gets inserted where 5 was. 10? And then after that we have 2, 3, 4, 5. And again, we're gonna ask is 1 larger than 5?

[00:03:11]
Move 5 to the right. Is 1 larger than 4? Move 4 to the right. Is 1 larger than 3? Move 3 to the right. Is 1 larger than 2? No, move 2 to the right. And eventually we reached the beginning of the list and we're going to insert it at index 0 which is gonna be 1, 2, 3, 4, 5.

[00:03:29]
So basically we just continually shift all the numbers over until eventually it finds like okay, this is where it goes and then we put it there and then we start the loop over again. Make sense?
>> Looks like reverse bubble so.
>> It kind of does, doesn't it?

[00:03:46]
Yeah, I could definitely see that logic. Yeah, this, I thought this graph was actually pretty helpful coz you can see them, shifting the numbers over until eventually they find where it's supposed to go. Is cuz you can see this number continually shift over. All right, so what's the big O of this?

[00:04:14]
What's the worst case scenario for this particular algorithm. Well, it's gonna be a reverse sorted list again, right? Because that means we're gonna continually have to shift everything over as much as possible, right? Every single time that we can shift something over, we're gonna have to do that until everything has to arrive at the beginning of the list from the end of the list.

[00:04:39]
So reverse sorted list, worst case scenario, best case scenario is you get a sorted list and nothing ever has to shift, right? We get one iteration through, nothing moves and everything works great. So what's the average case scenario? Well, the average case scenario is that more or less, you're gonna have some sort of shuffled array.

[00:05:03]
And most items gonna be compared against most other items and you end up with basically n squared. Now it is better than bubble sort coz it actually will do substantially left less work than bubble sort does. But it's still n squared, right? It's n squared with better coefficients.

[00:05:25]
Now, why is this still a useful algorithm? Let's say that you had an array that you were getting back from your database and it was mostly sorted. Let's say you knew ahead of time that is a list of length 100, and you know for a fact 98 of those are gonna be in a sorted order.

[00:05:46]
Insertion sort is really good for that, right? When you know that you have mostly sorted lists or totally sorted lists, insertion sort is really really good at handling those kinda situations and so that's when you would use an insertion sort over something like click sort and merge sort which have better average case but worst best case, if that makes sense.

[00:06:13]
Spatial complexity we're still at constant time because we're not creating any additional stuff on the fly. I mean, I guess we have some swapping and moving to do but for the most part, we're doing that like we're doing what's in place, right? So we're having destructive sort. So that's not too bad.

[00:06:35]
And I believe it is stable. Yeah. And yeah, insertion sort can be stable as long as you implement it as such. Okay. Does anyone have any questions about insertion sort?
>> I'm thinking it's like one of the interesting cases would be something like an event log from a server, where you think that it would be mostly sorted by time for example, but sometimes some events just don't follow the the order because the server received them a bit late and you have to fix those.

[00:07:20]
Is that a good case for using something like this?
>> Yeah, I can see that something like where you're maybe getting network traffic from a server and maybe it's like a UDP so it can come out of order or something like that. I could see insertion sort being useful in that case, typically network traffic is a priority queue, right?

[00:07:43]
So some network traffic is more important than other pieces of traffic in which case, priority queues always go together with heaps. We'll be talking about heaps later. But in the strict case of like you're getting a mostly sorted list of traffic back and you wanna make sure that it's in the correct order or messages or something like that.

[00:08:06]
Yeah, totally. I mean anything that's gonna be mostly sorted and you need it to be totally sorted cuz this is the perfect use case for that. And actually, sometimes we'll actually combine these sorts together. So you'll start maybe with an insertion sort, and if it goes for too many cycles, then you'll actually fall back into a like a quick sort.

[00:08:30]
So, you'll see like, hey, maybe this is already sorted, we'll check. We'll do like three iterations. And if we get beyond that, it's like, okay, this is too unsorted. We'll break down into quick sort or something like that. So you can actually kinda combine these together to get the the best case scenario of an insertion sort, but also cover the average case with something like a merge sort of quick sort.

[00:08:50]
So, we won't be doing that today but it actually might be a fun exercise for you to try as well.