Four Semesters of Computer Science in 5 Hours Interfaces Data Structure

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

[00:00:03]
>> Brian Holt: These are just interfaces that most of you will probably be familiar with because you've been interacting with them. You maybe have not been aware that you've been interacting with them, but you have been nonetheless definitely if you're in any amount of JavaScript, and you certainly have today.

[00:00:18] So if you're here you have already. Congratulations. So we're going to talk about data structures in kind of two parts. We're gonna talk about interfaces and then we're going to talk about implementations. So interfaces means that I know how to interact with it, but I have no idea how it works on the inside, right?

[00:00:36] So it's a black box that has a couple buttons that I know how to push, but I have no idea what the buttons actually do. Then the implementation is what's inside the black box. How does it actually work? So the first part, we're going to talk about the interfaces and then we're going to talk about the implementation.

[00:00:52] Okay? So we're going talk about sets first.
>> Speaker 2: Can we, hey, Brian?
>> Brian Holt: Yeah.
>> Speaker 2: I've got a few questions here.
>> Brian Holt: Sure.
>> Speaker 2: From Drew, this is related to a technically insertion sort but the last section. He's asking, translating this to the physical world most people probably alphabetize things with insertion sort, but would any of the other algorithms be more effective or efficient?

[00:01:25]
>> Brian Holt: That's a good question. I think the answer to that question is regardless of what you're sorting. Yeah, I think I can unequivocally state that regardless of what you're sorting, insertions sort is useful for things that are sorted or nearly sorted. Because it's going to run through only a couple of times.

[00:01:46] And then for everything else, either merge sort or quick sort's gonna be better. Depending if you need stability and if you need, if you may be feeding it a sorted list. So despite the fact that you ma, in your head be using insertion sort for some things
>> Brian Holt: Usually merge sort or quick sort, in fact almost always merge sort or quick sort is gonna be faster.

[00:02:14]
>> Brian Holt: Since we're talking about this, we'll just do something that I forgot to cover real quick, which is variations of Quick Sort. We just chose the pivot as last number. The most popular implementation i.e. the one that you're normally gonna do if you were to implement Quick Sort is called Quick Sort 3.

[00:02:35] So if you remember here.
>> Brian Holt: [INAUDIBLE] If I feed it a,
>> Brian Holt: I got to sort this again.
>> Brian Holt: Okay, so if I have, come on, just let me draw, okay, 1, 2, 3, 4, 5. If you remember correctly what I was showing you before, that is that 5 is gonna be the pivot and then everything is gonna be in the left.

[00:03:17] Right? And it's gonna keep doing that, which is really inefficient for Quick Sort. There's a implementation called Quick Sort 3 that kind of mitigates this risk. And what it does is it says, hey I have the first element, the middle element, and the last element. And I'm gonna pick the pivot that is in the middle of those three.

[00:03:38] So in this particular case, you're going to say okay, now my pivot is going to be 3. So it's slightly more than you need to do. Like if rather than just picking the last one, but this mitigates the case of having a sorted list because now my list is going to look like 1, 2 and 4, 5 which is decidedly much better.

[00:03:59] You're still leaving yourself up to like, what happens if I have a list of 1, 7, 1, 5, 1? That's still a problem and obviously that's not gonna really fix your problem. But I would say this is a much more smaller chance, right? The chances of you getting a sorted list is much greater, right?

[00:04:26] So that's called Quicksort 3, where you choose one of three pivots, the middle, the end or the first one. But there's other variations of, that I'm not aware of, that you can also look up as well.