This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.
Transcript from the "Bubble Sort" Lesson
[00:00:00]
>> Bianca Gandolfo: So we're gonna talk about sorting. How many people here have implemented some sort of sort on their own? Two or three of us, very cool. What's sort? Do you guys use sorting at work? Do you implement your own sorting algorithms at work? Or you just did it for fun?
[00:00:19]
>> Bianca Gandolfo: Everyone's now looking at me, this is really funny.
>> Speaker 2: [LAUGH]
>> Bianca Gandolfo: So, when did you implement a sorting algorithm?
>> Speaker 2: I did a binary exclusion as part of a class one time.
>> Bianca Gandolfo: Mm-hm, so, for school, cool. School, for fun? Suddenly no one knows how to talk.
[00:00:39] I have amnesia sometimes, so I understand.
>> Bianca Gandolfo: All right, cool, so sorting, sorting is super important. We do have a native sort method in JavaScript that we'll talk about. It does not use any of these elementary sorts, thank God, because what we're gonna learn is that they all kind of suck in terms of speed.
[00:01:01] But it is important for us to go through them. They're gonna be your basic naive implementation when you sit down in the chair and the scary interviewer is like, here is an unsorted list and blah, blah, blah, something, something, and you need to sort it. This is probably what you're gonna start off with your first stab.
[00:01:22] Unless you master one or both of our tecursive sorts later this afternoon, cool?
>> Speaker 3: My friend asked me if we were going to reverse a binary tree on a whiteboard.
>> Bianca Gandolfo: We are not gonna be doing any white boarding.
>> Speaker 3: [LAUGH] Yay.
>> Bianca Gandolfo: But yeah. If you're gonna be doing white boarding interviews, definitely practice this kind of stuff on a, we have one whiteboard, but that's broken unfortunately.
[00:01:51] But good question. Awesome. We're gonna start with bubble. So, basically how bubble sort works, and I'll just have this gif that should start working a second. So bubble sort just compares adjacent values and swaps the larger one up to the top. And so, it's called bubble sort because the higher numbers start to bubble up to the end and as we go up you'll see we'll start to, on the right, have a sorted array, and on the left we will have an unsorted array.
[00:02:34] Although this sort here is not optimized so it's not even thinking about that too much. Cool. There's something really important that I have to share with you. Which is this video, which is awesome.
>> Bianca Gandolfo: And I'll know if you guys are ready for this. But this is these Eastern European dances that implement, have you guys seen this before?
[00:03:00] My God, it's so good, are you ready? I don't know if you guys can hear it. No, Chrome doesn't play videos. Let me open Firefox. Does anyone else have that problem?
>> Bianca Gandolfo: Okay.
[00:03:21]
>> [MUSIC]
[00:03:24]
>> Bianca Gandolfo: Isn't this awesome?
[00:03:36]
>> [MUSIC]
[00:03:44]
>> Bianca Gandolfo: If I had free time, I'd be doing stupid stuff like this. Come on. They're gonna get started any second now. Here we go.
[00:03:56]
>> [MUSIC]
[00:04:06]
>> Bianca Gandolfo: Come on, start sorting.
>> Speaker 2: [LAUGH] Here we go.
>> Bianca Gandolfo: So we compare, 3 is greater, it goes up.
[00:04:15]
>> [MUSIC]
[00:04:19]
>> Bianca Gandolfo: Extra credit if someone learns this dance before tomorrow. [LAUGH]
[00:04:25]
>> [MUSIC]
[00:04:26]
>> Bianca Gandolfo: Cool, let's skip, I know you guys wanna watch all five minutes of it.
>> Speaker 2: [LAUGH].
>> Bianca Gandolfo: Let's skip maybe to like-
[00:04:34]
>> [MUSIC]
[00:04:37]
>> Bianca Gandolfo: Here, just to get the full experience. We are the YouTube generation. We can't watch anything for more than 30 seconds.
[00:04:48]
>> [MUSIC]
[00:04:50]
>> Bianca Gandolfo: And now it's sorted.
[00:04:54]
>> [MUSIC]
[00:04:56]
>> Bianca Gandolfo: Awesome. I just wanted to share that with you, because I just love any moment where these can be slightly more interesting, like any way.
[00:05:12]
>> [MUSIC]
[00:05:12]
>> Bianca Gandolfo: [LAUGH] All right, cool. So I have-.
>> Speaker 4: Have you see the D3 one?
>> Bianca Gandolfo: They have-.
>> Speaker 4: The sorting with D3?
>> Bianca Gandolfo: Mm-hm.
>> Speaker 4: Okay, I'll post the link.
>> Bianca Gandolfo: They are some good videos for that?
>> Speaker 4: It's not video, it's-
>> Bianca Gandolfo: It's a D3 visualization, maybe?
[00:05:34]
>> Speaker 4: Yeah. Micro Stock has a whole talk on visualizing algorithms.
>> Bianca Gandolfo: Cool. That's awesome.
>> Speaker 4: So you can literally type in, visualizing algorithms Micro Stock I'll past it into chat.
>> Bianca Gandolfo: Cool. All right.
>> Speaker 4: They have some really good stuff.
>> Bianca Gandolfo: So that's bubble sort. Again, we're comparing adjacent elements, swapping the bigger one.
[00:06:04] Swapping, swapping, swapping, starting over. Swapping, swapping, swapping, starting over. Swapping, swapping, swapping. Cool, pretty straightforward.
>> Bianca Gandolfo: Here's our interface. So bubble sort is a function, it takes a list and it returns a sorted list. It does some things in between, loops through it, maybe compares some, maybe swaps them.
[00:06:28] How is this interface different than when we were talking about the interfaces for a data structure?
>> Bianca Gandolfo: Anyone?
>> Speaker 5: Well, the ones where their data structures had a return value. This is more like a, I don't know. I guess that you could say this is returning a sorted list.
[00:06:56]
>> Speaker 2: Yeah, mm-hm?
>> Speaker 3: I fee like you would instantiate a queue or a stack.
>> Bianca Gandolfo: Yeah yeah yeah.
>> Speaker 3: And this is just a function you pass a list to, and it returns a sorted list.
>> Bianca Gandolfo: Yeah, exactly, so this is an algorithm. We're not doing any sort of class patterns here.
[00:07:12] It's just gonna be a function that takes an input, gives an output. That's what I'm looking for. So in our interface, we're not gonna have a constructor function. We're not gonna have shared methods. This is just a method, and maybe this method could live as a shared method on the data structure perhaps.
[00:07:34] So this is like sort of a zoom in of one of those methods that you might have on a prototype of some data structure. Probably not bubble sort because as you might have noticed, it's pretty slow that's why the video is like five minutes long.
>> Speaker 2: [LAUGH]
>> Bianca Gandolfo: But it works, it works, and if you just need something that works, I'm not judging.
[00:07:57] Cool. All right, so now it's over to you again. We're gonna pseudocode bubble sort. I'm gonna give you ten minutes to write out some pseudocode about how you think you can go about approaching this algorithm. Let's check it out. Here's my pseudocode. Mine says.
>> Bianca Gandolfo: For k, loop through 1 to n-1.
[00:08:34] For i, loop to 0 to n-2. If the first one is greater than the second one, or the next one, right, adjacent, switch them. Bubble sort. Anyone do it differently?
>> Speaker 4: While loop.
>> Bianca Gandolfo: While loop. Instead of the other one.
>> [INAUDIBLE]
>> Bianca Gandolfo: Okay, cool. No? Okay, so that's the pseudocode for bubble sort.
[00:09:07] We're gonna jump into how do we analyze the run time of bubble sort? Cool. So, our loop, ( n- 1 ), right, because we're only looping to the end. Next one, ( n- 2 ), right? Which probably isn't gonna matter later. Remember that these smaller things don't really matter.
[00:09:33] Then we have some constant swaps and things like that, yeah?
>> Bianca Gandolfo: Cool, so again, since they're nested, we multiply them. And you can use a polynomial expander if you want, or you can do it yourself. If you wanna like hark back to, what's that? Trigonometry, precalculus or something?
[00:09:58]
>> Speaker 3: Yeah.
>> Bianca Gandolfo: But it comes out to this.
>> Bianca Gandolfo: Where really all we care about is the n squared. So if you add it all up, or multiply it all up and then expand it, it'll look like this. But at the end of the day, we consider this an n squared algorithm.
[00:10:19] So yeah, there is some math that you can do if you're into that. But when we're thinking about it, we only think about it in terms of n squared.
>> Bianca Gandolfo: Cool, any questions?
>> Bianca Gandolfo: Is everyone clear how we got this?
>> Speaker 4: Can you explain the first two things, k and i?
[00:10:48]
>> Bianca Gandolfo: k and i. Yeah that's like when you say for i = 0, for k = 0, or j, just a variable name. So this is a variable name in our loop.
>> Bianca Gandolfo: This is just sort of like a standard pseudocode kind of wording.
>> Bianca Gandolfo: So you're looping through and all the, for every loop this is gonna be incremented from 1 to n- 1.
[00:11:19] So the first loop k will be 1, the second loop will be 2, etc. And then for i, I'll start at 0 and we'll go to n- 2.
>> Speaker 4: So n is the length of the-
>> Bianca Gandolfo: Of the list.
>> Speaker 4: Yeah, yeah, okay.
>> Bianca Gandolfo: Yeah, exactly, exactly. So a is our array, we have i, i + 1, and we swapped them.
[00:11:46]
>> Bianca Gandolfo: Cool, since they're nested, we multiply them. This is called a polynomial. That's not really important. All we need to know is at the end of the day it goes to n squared. If you can see that pattern and you can make that estimation, that's all you need to do.
[00:12:02] But if you're interested in that, you can also do it more specifically if you'd like.
>> Speaker 4: What's k in this?
>> Bianca Gandolfo: k is the variable in the loop when you say 4 of our i. Yeah.
>> Speaker 4: It's just the editor.
>> Bianca Gandolfo: Mm-hm. Yeah, great. So we have some nested loops in here.
[00:12:23] We know that's gonna be n squared. Doesn't it feel nice? You can dust off the math. Except for our mathematician David, he's probably sad. But everyone else is probably relieved. Do we feel relieved? A little bit? Less intimidated by it, perhaps, hopefully. Okay, cool.
>> Speaker 4: Yeah, and of course you can just replace the n- 1 with n instead of expanding, right?
[00:12:54] Unless you like multiplying.
>> Bianca Gandolfo: Yep, absolutely.
>> Bianca Gandolfo: All right so, you could optimize it a little bit, and not loop all the way to the end. And then we have something called n-k-1. Because we're not going to the end as the end of our loop is sorted. Do you have a question?
[00:13:21]
>> Speaker 5: You want the inner loop to have a k in it, right? Not the outer.
>> Bianca Gandolfo: Yeah you might be right there, thank you. Either way, the point here that I'm trying to make is that at the end of the day this is still n squared. So even if we optimize this a little bit, still gonna be n squared, so there we are.
[00:13:45] Bubble sort, n squared, space complexity, constant, cuz it's in place.