Brian introduces the concept of interfaces and how they behave like a black box. They provide details about how they can be used without exposing their implementation. Before moving into the first interface topic, Brian answers a few lingering audience questions about sorting algorithms.
Then the implementation is what's inside the black box, how does it actually work. So the first part we're gonna talk about the interfaces, and then we're gonna talk about the implementations. Okay, so we're gonna talk about sets first. - [Woman] Hey, Brian? - Yeah. - [Woman] I've got a few questions here. - Sure. - [Woman] From Drew, this is related to quick, technically insertion sort, but the last section? - Sure. - [Woman] 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?" - 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 insertion sort is useful for things that are sorted or nearly sorted because it's gonna run through only a couple of times. And then for everything else either mergesort or quicksort'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 may in your head be using insertion sort for some things, usually mergesort or quicksort, in fact, almost always, mergesort or quicksort is gonna be faster. Since we're talking about this, we'll just do something that I forgot to cover real quick, which is variations of quicksort. We just chose the pivot as the last number. The most popular implementation, i.e. the one that you're normally gonna do if you were to implement quicksort is called quicksort three.
So, if you remember here... It's a... If I feed it a... Come on. Oh, I gotta start this again. Okay, so if I have, come on, just let me draw. Okay. One, two, three, four, five.
If you remember what I was showing you before, that is that five is gonna be the pivot, and then everything is gonna be in the left, right? And it's gonna keep doing that, which is really inefficient for quicksort. There's an implementation called quicksort three 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, right?" So in this particular case you're gonna say, "Okay, now my pivot is gonna be three." So, it's slightly more than you need to do, right? Rather than just picking the last one, but this mitigates the case of having a sorted list.
Because now my list is gonna look like one, two and four, five, which is decidedly much better, right? You're still leaving yourself up to like what happens if I have a list of one, seven, one, five, one, right? 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? So that's called quicksort three where you choose one of three pivots, the middle, the end, or the first one.
But there's other variations that I'm not aware of that you can also look up as well.
Note: This course was created by Frontend Masters. It was originally released on 07/12/2016. We're pleased to host this training in our library.
- Big O
- Sort: Bubble, insertion, and merge,
- Median values
- Set, map, stack, and queue
- Array lists and linked lists
- Binary search tree
- AVL tree
- Single rotation and double rotation
- Hash table
- Functional programming
- Map, reduce, and filter