The bubble sort algorithm is typically the easiest to conceptually understand, but the least efficient in execution. It continually loops through an array comparing adjacent indexes until the entire array is sorted. Brian uses a simple array of values to demonstrate the bubble sort order of execution and Big-O value.
(oriental music) - We're gonna leave recursion behind for a little bit. In other words, don't use recursion until I tell you again to use recursion. These are all gonna be done using loops, but recursion is a building block that we need to have in our in our abilities to be to do some of these other problems. So a lot of algorithms come down to sorting, and 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 (laughter) as in, you're not ever gonna use bubble sort in production code. 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 sort is I have... Let's see, diagram that out.
And pen, black, here we go. So if I have numbers like five, that's good. - [Female] Hey Brian. - Yeah? - [Female] Before we get too far into this, we still have a question on the last exercise. - Sure. - [Female] Damien is asking if, he's wondering if N less than two, return N works, he says that all test pass? - N less than two, yeah, that totally works.
- [Female] Okay. - Yeah, it's maybe a slightly less efficient, but you have one additional call, right? So maybe if your call stacks at 255 and it pushes it 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. 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 and is like, oh, it just returns one, right? Whereas they have to reason about it, it's like, okay, well, if it's less than two, then it's just gonna return one, right? They have to reason about that.
Not that that's that hard, but if that works for you then more power to you. Good question, okay, so let's talk about bubble sort here. So if we have a list of like five, seven, six. Bubble sort is we're gonna compare two numbers at a time, and then we're gonna swap them if they're out of order. Let's actually do this, so a four's in here as well.
Okay, so we're gonna have an outer loop that's gonna go around the numbers, and an inner loop that's going to compare those numbers, right? So the outer loop is gonna go through... I explained that incorrectly, 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 gonna go through and swap numbers if they're out of order. Okay, so five and seven, in order, no swap.
Seven and six, out of order, so we're gonna swap them, so let's just five and then we're gonna swap six and seven, right? And then at this point, seven and four are out of order so we're gonna swap those as well, so it's gonna be four, seven, right? And at the end of our first iteration, it's gonna be five, six, four, seven, right? Now something was swapped in the previous iteration, so we're gonna do that again.
So I'm gonna clear this and do that again. So I think it was five, six, four, seven, thank you. Okay, so we're gonna run the same algorithm, five and six, still in order, those get put down, six and four, those are out of order, so we're gonna swap those. Five, or four, six and that's in order, so that's going to be, something was swapped in the previous iteration, so in this particular case, we're gonna do four, five, six, seven, right? Cause those ones are all still in order.
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. Okay, so you're gonna have a do-while loop where the outer loop is gonna go through while something has been swapped, right? And then you have the inner loop that's gonna go through and say, is X and X or N, N and N plus one, are they out of order? Okay, swap, are they not, leave it, and then it just moves on and keep swapping things until they come back in order. And 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? So what does that end up being, N squared, right? Cause we have an inner loop and an outer loop. And this is again wildly inefficient algorithm, but hopefully now you've conceptualized exactly how it works. So it is a good teaching tool.
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