Bubble Sort

[00:00:00]
>> All right, so for the first code that we're gonna write today, we're gonna be writing bubble sort. Now bubble sort is actually not a algorithm that you're ever going to use directly in production. Because there are algorithms that are just strictly better than bubble sort, but it really fits super well with the mental model that humans would think of how to sort numbers.

[00:00:25]
So the first thing I'll tell you today, a lot of algorithms is about sorting. We're gonna be doing, I think, six different sorts today. And the reason for that is it's demonstrative of the ability to write algorithms in the sense of we're trying to show how you can take a large set of numbers and do a holistic action with them.

[00:00:49]
And the various different strategies that you can do to minimize the work that that you're doing, and which is to say that you may not ever write quicksort or merge sort, insertion sort directly. In fact, I imagine you never will because the language is actually better at doing it than you are.

[00:01:08]
But you will be able to take apart these algorithms and use them kind of piecemeal here and there. I remember I've interviewed at Facebook years and years ago to be on the React core team. And the algorithm that I used to solve the question that they asked was actually merge sort, just kind of dissected and reput back together.

[00:01:32]
So that's kind of the mindset I want you to have here is you're probably not gonna sort too many numbers directly by hand, by code, but you will use these algorithms kind of pieced apart and reapplied. Okay, so I'm just giving you some justification of why I'm gonna have you sort so many damn numbers.

[00:01:53]
So this is kind of a fun little graphic. It's from Wikipedia of how bubble sort actually looks over time. And the way that works, you can see that the biggest numbers bubble up to the top, right? That's why it's called bubble sort is cuz the biggest numbers over time end up being bubbling up to the top, and then it sorts the smaller part of the array over time.

[00:02:18]
And the way it works is this, is you're just gonna go over the array, and if the item at index one is bigger than the item at index two, then you're gonna swap index one and index two, right? And then you're just gonna keep doing that. You're gonna say, is this one bigger than this one?

[00:02:38]
No, okay, next item, is this one bigger than this one? Yes, swap them, right? And then you just kinda swap them. So let's look at kind of a drawn out version. So let's say we're gonna sort this one here, 1, 5, 4, 3, 2. The first question you ask starting at the beginning, is 1 and 5 out of order, right?

[00:03:00]
Is 1 larger than 5? It's not, right? Next thing, is 5 larger than 4? Yes, then you swap. And then you end up with an array that looks like this 1, 4, 5, 2, 3. Now, notice here that 5 is the largest item in the array. So is it larger than those things?

[00:03:22]
The answer is always going to be yes, right? So that's why 5 is going to bubble to the top. So are 5 and 2 out of order? Yes, swap, are 5 and 3 out of order? Yes, swap, and now we've gone through the entire iteration once, right? We've gone through the entire array.

[00:03:43]
Is it sorted yet? No, right, 4 is still here out of order. So that's kind of the inner, or sorry, yeah, what we did here, this is the inner loop, which is asking, are the two numbers out of order? And then there's an outer loop that says, hey, during my last iteration, did anything swap?

[00:04:06]
If the answer to that question is yes, then you do it again. If you go through it and nothing swaps, that means the array is sorted and you're done, right? So end of the array, did anything swap? The answer is yes. So then we start all over again.

[00:04:24]
1 and 4 out of order? No, 4 and 2 out of order? Yes, so you swap those. Are 4 and 3 out of order? Yes, swap, and we've reached the end of the array again. Now notice we don't have to ask, are 4 and 5 out of order?

[00:04:39]
This is a bit of an optimization. You don't actually have to do this. But after the first iteration, you can guarantee that the last item in the array is definitely the largest item, right, because it'll bubble to the top. Which means we can progressively look at less than the rest of the array.

[00:04:56]
So after two iterations, we can guarantee that the last two items are definitely the largest two items in the array, right, due to the method of how bubble sort works. Okay, so are 4 and 5 out of order? No, in fact, so this question here was technically unnecessary.

[00:05:17]
You hit the end of the array, did anything swap? The answer's yes, we had a couple swaps here. And now notice it actually is sorted, right 1, 2, 3, 4, 5. But because something swapped in the last iteration, we have to go through it again, right? [COUGH] So are 1 and 2 out of order, 2 and 3, 3 and 4, 4 and 5?

[00:05:37]
And then here, we hit the end of the array and nothing swapped. So now we know this is in order. So since nothing swapped, we break the outer loop, and we're done, right? So that is the end of that particular sorting algorithm. So I talked about this a little bit, which is after the first run through, the largest item's at the end.

[00:06:05]
After the second iteration, the second largest item's at the end, so on and so forth. Cool, so that's optimization right there. It would make a difference in the coefficient. It wouldn't actually make the big O any better. But it does guarantee that it'd run a little bit faster.

[00:06:29]
So what's the time complexity? What's the computational complexity of this algorithm?
>> Someone online is saying, the best case scenario is four of n.
>> Yep, so let's talk about the average case first, and then we'll loop back to the best case.
>> And they're saying the average case is O of n squared.

[00:06:51]
>> Yeah, so there's gonna be an outer while loop, right? That's gonna say while something swapped, then continue doing the inner part of that loop, right? And then the inner loop is gonna be a for loop, which is going to loop over the array every single time, right?

[00:07:12]
So we have a outer while loop and an inner for loop. What does that look like? It's gonna be n squared, right? So that's gonna be the average case and it's also gonna be, well, we'll talk about worst case here in just a second. But the average case here is that we have an outer loop and an inner loop, which means we're gonna end up with n squared.

[00:07:37]
Because every item in a bubble sort more or less has to be compared to every other item in the array. That's kinda the question that you're gonna ask yourself is, does every item in the array, at some point say, is this larger than this? And the answer for a bubble sort is yeah, every item will see every other item in the array.

[00:07:57]
So that's gonna make the average case of this n squared. The worst case scenario for a bubble sort is a reverse sorted list. So if this came in as 5, 4, 3, 2, 1, that means that we're gonna have to do a lot of swapping, right? And we're gonna have to ask, is this greater than this?

[00:08:19]
So that's gonna be the worst case scenario is a reverse sorted list. The best case scenario is going to be n, which is going to be a sorted list, right? Cuz if this was 1, 2, 3, 4, 5, it would go through the array once and say, hey, we did no swaps, I'm done.

[00:08:44]
What's the spatial complexity of this? It's just, sorry, go ahead.
>> [INAUDIBLE]
>> It's constant, that's correct. We're not creating any additional arrays. We're not doing anything like that. We're just operating on the array itself, which means that no new memory is being called into use here, which means it's gonna be constant time.

[00:09:14]
Okay? So the next question, which we haven't talked about yet, is this sort stable? And again, we haven't talked about that yet. A stable sort that says if two items are considered equal in this sort, are they guaranteed to be in the same order when they come back?

[00:09:40]
So here, I have a little array that says state, which has Sarah Dresner, Shirley Wu, and Scott Moss. Scott and Shirley both live in California. And let's say we were sorting by state. For this to be a stable sort, we'd have to guarantee because Shirley came first in the array that she would come before Scott.

[00:10:05]
Some sorting algorithms do not guarantee that, right, that if one of them comes first, it may not come first when it comes back, and that would be an unstable sort. Sometimes that's important to you. Sometimes that's not important to you. So in this particular case, Yes, bubble sort is considered a stable sort, right?

[00:10:35]
Because you just would never swap them, which means that in this particular case, Shirley would be guaranteed to be ahead of Scott if we did this sort based on speed. And the last one that we didn't talk about is this sort is what's called destructive. That means that it's actually operating on the array itself.

[00:10:57]
So if I pass an input into bubble sort, it's going to operate on bubble sort or the array itself, which means that if I wanted to keep a copy of the original unsorted array, I would have to make a copy beforehand, right? Some sorts will return brand new arrays and do not operate on the original array, which those would not be destructive.

[00:11:24]
But in this case, bubble sort is destructive cuz it's actually modifying the original input. Which if any of you are functional programmers, that feels really gross, right? But sometimes that's a good thing, right? Because we're not increasing some of the spatial complexity. So again, it's a trade-off. In this particular case, it's okay to operate on the original input.

[00:11:48]
And you should in this particular case. So again, functional programmers love rules. Never operate on the input. And I want to refer you back to our trade-off's number one rule, there are no rules, right? So in this particular case, we want to modify our inputs.