This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Bubble Sort" Lesson
[00:00:00]
>> [MUSIC]
[00:00:03]
>> Brian Holt: We're gonna leave recursion behind for a little bit, in other words don't use recursion until I tell you we're gonna use recursion. These are all going to be done using loops, but recursion is a building block that we need to have in our abilities to be able to do some of these other problems.
[00:00:22] So a lot of algorithms come down to sorting. That's because sorting numbers is a very useful thing in computer science, and there's many ways to skin a cat in this particular case. First one we're gonna talk about is bubble sort. Bubble sort is not useful. [LAUGH] As in you are not ever going to use bubble sort in production code.
[00:00:49] It's a very useful learning tool, though, because it very well applies to the way that we as humans think about sorting numbers in our head, right? The basic gist of bubble store is I have a, let's see, diagram that out.
>> Brian Holt: And pen, black, here we go. All right, so if I have numbers like 5, that's good.
[00:01:21]
>> Speaker 2: Hey, Brian?
>> Brian Holt: Yeah.
>> Speaker 2: Before we get too far into this, we still have a question on the last exercise.
>> Brian Holt: Sure.
>> Speaker 2: Damien is asking, he's wondering if n less than two return n works? He says that all tests pass.
>> Brian Holt: n less than two, yeah, that totally works.
[00:01:44]
>> Speaker 2: Okay.
>> Brian Holt: Yeah, it's maybe a slightly less efficient but you have one additional call, right? So maybe if your call stack's at 255 and it pushed to 256 and you have a stack overflow it might be a problem, but if that makes more sense to you, I think that's totally fine.
[00:02:02] The reason probably why I would err on the side of using one is it's very explicit, right? It's very easy for someone to come later who's like, it just returns one, right? Whereas they have to reason about it, it's okay, well if it's less than two then it's just going to return one, right?
[00:02:16] They have to reason about that. Not that that's hard but that works for you, then more power to you.
>> Brian Holt: Good question, okay, so let's talk about bubble sort here. So if we have a list of 5, 7, 6, okay? Bubble sort is where we're gonna compare two numbers at a time and then we're going to swap them if they're out of order.
[00:02:44] Let's actually do this so 4 is in here as well. Okay, so we're gonna have an outer loop that's going to go around the numbers and an inner loop that's going to compare those numbers, right? So the outer loop is going to go through, I explained that incorrectly.
[00:03:02] So the outer loop continues running as long as there are numbers swapped in the previous iteration, right? So the outer loop is always going to run at least once. The inner loop is going to go through and swap numbers if they're out of order, okay? So 5 and 7, in order, no swap.
[00:03:19] 7 and 6, out of order, so we're going to swap them. So it's just 5 and then we're gonna swap to 6 and 7, right? And then at this point 7 and 4 are out of order. So we're going to swap those as well. So it's going to be 4, 7, right?.
[00:03:39] And at the end of our first iteration it's gonna be 5, 6, 4, 7, right? Now something was swapped in the previous iteration the so we're going to do that again. So I'm gonna clear this and do that again.
>> Brian Holt: So I think it was 5, 6, 4, 7 thank you, okay?
[00:04:05] So we’re gonna run the same algorithm, 5 and 6 still in order those get put down. 6 and 4, those are out of orders o we're gonna swap those. 5 or 4, 6, and that's in order so that's going to be, something was swapped in the previous iteration.
[00:04:22] So in this particular case we're going to do 4, 5, 6, 7, right, cuz those ones are all still in order. Now, it's in order right now, right? We know that looking at it, however, the computer doesn't know that yet, right? So something swapped in the previous iteration so it's going to go through again.
[00:04:39] And because nothing's gonna swap in that last iteration, it's [SOUND] okay, done. And then bubble sort's finished. So, to recap you have an outer loop. It's going to be a while loop that runs once, right? Runs at least once, which that's a do-while loop, right? Most of us don't use do loops very much in JavaScript.
[00:05:00] I can't actually remember a time if I've professionally used to do loop, but we're gonna use it here. You can model that with a while loop as well, but this is one of the only times you get to use a do loop so you might as well do it.
[00:05:15] Okay, so you're going to do-while loop where the outer loop is going to go through while something has been swapped, right? And then you have the inner loop that's going to go through and say, is x and x, or n, n and n plus one are they are out of order?
[00:05:27] Okay, swapped, are they not? Leave it, and then it just moves on and keep swapping things until they come back in order. You see here this diagram kind of shows you what that looks like over time. So what's the Big O on this? Well we have an outer do-while loop and we have an inner for loop, right?
[00:05:54] So what does that end up being? n squared, right, cuz we have an inner loop and an outer loop. And this is a, again, wildly inefficient algorithm but hopefully now you've conceptualized exactly how it works. So it is a good teaching tool.