Bubble Sort Solution

[00:00:00]
>> Bianca: I hope that you took a stab at Bubble Sort. Let's take a look at the solution. So there is a few different ways you can implement Bubble Sort. This first one here is a naive Bubble Sort where we aren't optimizing for any cases. So with Bubble Sort, if you loop through an array without swapping anything, that is a sign that your array is already sorted and so you can just break from your loop.

[00:00:33]
So, that's one optimization of Bubble Sort. And for example, you can see that this solution does not do that. And then we have our optimized version here, where we are keeping track of the swap. So if there is an iteration where we don't swap anything, then we'll just return it.

[00:00:55]
So it's gonna short circuit any extra looping when there's no more items to be swapped. So if you're working with a mostly sorted list, Bubble Sort is actually an okay sort. If you're dealing with a reverse list than it's terrible. So, that's Bubble Sort. We can check out,

[00:01:24]
>> Bianca: When we run it. You can see when we have our basic implementation with the two loops, that each time it's going to run it.
>> Bianca: It's going to run the outer and inner loops the same amount of times. When it's randomly out of order, it's gonna swap it 21 times.

[00:01:46]
When it's already ordered, there are no swaps. And if it's reversed then it's a bunch. However when we optimize it, when we go through it, we just loop through it one time. And so it's a linear solution if the list is sorted. But again, we think about worse case, and so here's our worse case which is gonna be a quadratic solution.

[00:02:15]
So, that's Bubble Sort. There's a few different other sorts in the naive category. I encourage you to check them out online and implement them for yourself.
>> Bianca: They're pretty fun.