Bubble Sort

[00:00:00]
>> So of course, you have to do sorting. So normally, when you look at algorithms books, it often starts at sorting. I think search is just a simpler concept to understand because it's very, very practical whereas sorting often gets into this weird world. And so I wanted to start at search.

[00:00:19]
But now we're gonna do sorting. We are gonna implement two sorting algorithms, but one of them has to come a bit later. And so the first sorting algorithm I want to do is bubble sort. Now normally it starts off with insertion sort, but the problem with insertion sort is the example always sucks, it's like a card deck.

[00:00:35]
I still don't know how to sort cards. It's like it's always a much harder sort to start with which I'm surprised that we start that way. Cuz bubble sort is not only really, really, really easy to visualize exactly what's happening, it's also three lines of code. It's an extremely simple algorithm.

[00:00:52]
And my teacher once said, Ray Babcock, he once said if an airplane was going down, stewardess [SOUND] kicks the curtain between first class and economy because I'd be traveling and economy, and she said, quickly, we need someone that can write a sorting algorithm or this plane will crash.

[00:01:09]
You could write Bubblesort under a plane crashing, it is that simple. And so we could go over it cuz I just feel like it is the greatest of all sorting algorithms. And so hopefully our plane does not crash, but let's get this sorting algorithm going. So let's talk about bubble sort.

[00:01:25]
So the general definition or the quote unquote mathy definition of a sorted array is simply this. Any x sub i, meaning any ith position within the array, is going to be less than or equal to any i + 1, right? Does that make sense? This is true for the entire array.

[00:01:43]
That's how you know an array is sorted. So that's kinda like the mathy way of saying it. And so if we have an array that's not sorted, this property does not hold true universally. It may hold true in specific instances but not universally or universally. So let's start off with this array.

[00:01:59]
1, 3, I'm gonna make this up as we go, 4, 2. And I always wanted to memorize all these great examples so when I did it I could produce the best outcome, but I can never remember the example I'm gonna do, so we're just gonna make it up on the spot.

[00:02:12]
So how bubble sort works is that it starts in the zeroth position. And it's gonna go to the end of the array. And what it's gonna do is it's gonna say, hey, person next to me, the plus one next to me, if I'm larger than you, we swap positions.

[00:02:29]
That's the entirety of the algorithm. Boom, we've just done it, we're pretty good. So what happens? Let's actually go through and see what happens. So 1 goes to 3. Am I larger than you? I'm not. All right, so then we go here. Hey 3, am I larger than 7?

[00:02:43]
I'm not. Hey 7, are you larger than 4? You are? Well, fantastic. I'm gonna put 4 here. We're gonna put 7 here. Hey 7, are you larger than 2? You are? Fantastic. So what happened to our array by the end of this? By a singular iteration, what happens in bubble sort?

[00:03:11]
The largest item is where in the array? It's at the end. So a singular iteration will always produce the largest item in the last spot. So this is actually kind of unique, right? So that means the next time we do the bubble sort, the bubble sort, whatever, the Facebook as well.

[00:03:31]
The next time we do bubble sort, it means we only have to go up to but not include the last position, because that is already sorted, we don't need to look there. So if I rewrite my array, 1, 3, 4, 2, 7, now let's do bubble sort again except for we only need to do it right here.

[00:03:51]
So again, 1 says to 3, am I larger than you? No, 3 says to 4, am a larger than you? No, 4 says to 2, am I larger than you? Yes, I am, let's swap, awesome. And so, oopsies, I just [INAUDIBLE]. Again, we're done. The next largest value is in position, and we have a portion of the array that's sorted and a portion of the array that is not sorted.

[00:04:17]
So let's rewrite it again. 3, 2, 4, 7, and of course now we're just down to this. So we re-walk this next progressively smaller iteration. Do it again, it's going to end with a 3 right here, 2, 1. I actually had my entire array sorted at this point, but we would keep running until we have only one position left.

[00:04:37]
Cuz when you have one position left is your array sorted? It's always sorted. An array of one element is always sorted. So there we go. We did this. Now let's kind of abstract this cuz we also need to figure out the running time of this algorithm. Cuz this is kind of a unique algorithm, right?

[00:04:54]
The first time we do it, we do effectively n checks, right? We have to go over the entirety of the array. The second time we do it, well we don't have to do all of them, right, we can do n-1 checks effectively. Well, then the next time we don't have to do it again.

[00:05:12]
And then of course we keep on doing this until effectively we reach this point, right? Does that make sense? We are now down to the very last element. Now, some people they recognize this right away, right? This is a very familiar pattern that you should probably be familiar with.

[00:05:29]
For those that don't know about this, there's a fun little story and I'm gonna say it now. Sorry that it does contain a curse word, Mark, hopefully you'll forgive me. But effectively, there's this asshole in third grade named Gauss. And he was known as being a complete jerk.

[00:05:46]
And his teacher, very frustrated with all of the kids, one day said, kids that's it, everyone's sit down. I want you to add numbers from 1 to 100. Gauss, still in asshole, did it in about ten seconds. He was completely done right away, went up and showed his teacher.

[00:06:01]
His teacher said no way, this is not true. And of course, it was true. And this is what he showed her. It's that if you think about it, this is 101. You just add those two numbers. Well, what do you have left? Well, you have 2 to 99.

[00:06:15]
All right, well, let's add those two numbers. What do you have? 101. You can kind of tell where this is going. It's gonna keep going until you have 50 and 51, right? Awesome, so really, if you think about it, you could just do 101 times 50 and you have the answer.

[00:06:37]
But of course, we're computer scientists, we abstract this formula, so what do we do? Well 101, and this was 100, I mean to me that's n plus 1, right? 50, well you know what that looks like? That looks like n divided by 2. And if you run this and you do it, it works every single time.

[00:06:59]
N plus or n times n plus 1 all over 2 just will tell you the sum of numbers between a range. And so the reason why I make that or I say that story is my math teacher told me that story, then went on to tell all the reasons why Gauss was such a jerk.

[00:07:13]
But he was also extremely smart. I think his middle name was Friedrich, Friedrich. Anyways, fun story. But this always stuck with me because of that story. And I always remembered it, because now I have it locked away in my head. And if you look at this, if we just reverse that, you know what we'd have?

[00:07:28]
1, 2, 3, all the way up to n, right? We now know the formula, which means we have n plus 1, n over 2, let's break it all down, do the whole mathy thing. Well, first thing we can do is we can just drop constants, right? Because this is of course, big O, we're not concerned about constants.

[00:07:49]
So that means it's n squared plus n, all right? Well, in big O land, a thing you will do is drop non significant values, meaning this right here. I believe the term is actually insignificant values. There we go. It's n squared. So that is the running time of this algorithm is it's n squared.

[00:08:11]
And the reason why you drop this is just imagine the input even at 10,000, right? And 10,000 n squared is like, I don't even know what that value would be, 100 million I think off the top of my head. But either way, it's so insignificant at some point, it just eventually goes to zero.

[00:08:31]
As n goes up, insignificant polynomials go down. The same thing with n cubed versus n squared.