Implementing Bubble Sort

[00:00:00]
>> So there you go. So that is the running time of Bubble sort. And I'm very thankful that a third grader, who makes me feel stupid, actually was able to solve this for me cuz now I have the value right here. And of course, you know what we can do?

[00:00:13]
We can implement this. And I think we should implement it because it's so dang simple. And it'll also be your first sorting algorithm which anyone doing an algorithms class has to at least implement one sorting algorithm. So I do expect everyone to open up their editor immediately, okay?

[00:00:27]
You don't have to, I mean, you don't have to. But let's look up the bubble sort, up and up bubble sort and it comes with an array and of course, a sort in place algorithm. So hopefully everyone can do this, follow along. So again remember our algorithm. We need to be able to translate the ideas in our head into code.

[00:00:46]
So what I'm gonna do is I'm gonna create another one of these, and let's just kinda think about it in the abstract terms, we have an array from 0 to N. And we need to start at 0 and go up to, but not including N or (N- 1), because of course we're gonna take i and compare it to i + 1.

[00:01:06]
So we don't wanna go off the array. If we are using a more traditional language and you went off the array what happens? Array out of bounds exception if you're in Java? That's I think what I had the program is, if you're in C++, you have yourself I don't know what happens but things happen if you go off the array.

[00:01:21]
So we don't wanna do that, I don't wanna be reading HTML here, htat's the hackers language. And so what we want to do is go up to this, we want to go up to but not including N- 1. Okay, so that seems pretty easy, right? So we're gonna go for i up to say n, right, that's our thing.

[00:01:39]
We need to do this n times, right? We got to keep on bringing that number down until 0, and that means our inner loop needs to be the one that's actually gonna be doing the special magic and doing all that. So it needs to go up to n -1 but remember every single time we do a loop the last item becomes sorted so we can also minus i, does that make sense?

[00:02:03]
We keep getting progressively smaller as we go for the 0 with case, we go up to n- 1 for the first case, we go to n- 2 for the second case, we go to n- 3 etc. And from that point, the only thing we have to do is do a simple comparison, right?

[00:02:21]
If the array i is greater than array j, swap, right, (i, j) that's really all we have to do, right? I mean, that's the extent of the algorithm. It's extremely simple algorithm. There we go. Obviously, when we write this out, this will be a little bit bigger. All right, so let's just write that thing out.

[00:02:45]
We have the idea in our head. So of course we always do, I'm positive all the JavaScript people aren't used to writing out four loops, raw four loops, I think I've seen it called on Twitter. But this is just what you gotta do in the real world, you gotta write these four loops.

[00:03:00]
So let's go here, let's do an i and j loop. Awesome, so hopefully everyone has that. Now we neither do something with the j loop remember. We gotta up too but not include also the last element at the first iteration cuz we're gonna do a plus 1, remember that so let's minus 1.

[00:03:17]
Then remember every single time we execute the last element becomes the largest element we don't need to redo that so we're also gonna minus i. Does that make sense? There we go, we've now translated this code into this code, it's just a little bit more mechanical, not too bad.

[00:03:36]
So if array j is greater than array (j + 1) well, now we need to swap, swapping always not all that bad const temp equals array j, whatever your first line is you just repeat array j equals array (j + 1). Copy that and go array j + 1 temp.

[00:03:57]
There you go. Simple swap, right? I should have just created a function that anyone could use. I don't know why didn't you just have to write it yourself, there we go. And now this should be effectively Bubble sort so I jumped back here and pxjest bubble Michael bubble 8.

[00:04:14]
That would have been so much if I should have called the file Michael Bubble I'd have been great, there we go. And so now we've just written Bubblesort, it's really not all that hard this is an extremely simple algorithm to be able to do, you should just be able to do this first try for the most part.

[00:04:31]
I mean, I just did it first try so everyone can do it first try, right? But I mean, if you really think about it's actually a very concrete simple algorithm. It's probably simpler than binary search. In all technical perspective, binary search is significantly harder than this array or than this sorting problem.

[00:04:45]
We did it, awesome. Your first sorting algorithm, how does it feel? Is everyone pretty excited about their first sorting algorithm? Hello, I'm excited. All right, there are other sorting strategies I want to talk about but sorting algorithms are gonna deal with recursion and I haven't recovered recursion yet.

[00:05:07]
And so until I cover recursion, I don't want to go into that because I want to make sure everybody is on the same. And page when it comes to recursion because the problem with recursion is recursion of course and you don't really understand it until you completely understand it or feel like.

[00:05:20]
I felt completely lost and then all sudden I felt like I understood it completely. There's no middle ground, I felt like, it's not less sort of understanding. Now, it's just either get it or don't. It's a very painful concept. All right, any questions I've only ever had to implement a sorting algorithm one time, so very very rarely.

[00:05:41]
>> Since we are comparing each element of an array with another element of an array? It's kind of n square but I just didn't understand that n into n + 1 by 2, how did we came up with.
>> Yes.
>> Come up to that.
>> So the first part of your question was we're comparing two elements of an array so that's n squared.

[00:06:01]
But how did I come up with that formula and all that, I can go over one more time. So remember so that's why I did the very fundamental thing, when you access an array what is the runtime of accessing an element in the array. Is that fixed computational cost so it's of one right, every time we access of one.

[00:06:21]
So if we access an array twice, it's just two constant right, so this all constant operations, everything in here is constant. So this part of the operation is constant, nothing in there is based on input size it's all constant. It's really just these two that cause the squared algorithm because we're going over the length of the array and every time we go over it we go over some or most of the array every single time so we go over n.

[00:06:48]
And so now how does this thing we can go back to this proof. So I'll just kind of go back to the simple version of it all? Remember, I'll just kind of re-explain it just because the reality is we're doing nothing different than summing all the values. Cuz if you think about it, we're gonna run n times the first time, actually well technically the first time we run n-1 amount of iterations through the loop.

[00:07:14]
If you look at the code we're running the very first time we were running n-1 amount of times. The next time we run n- 2 because i becomes 1, we subtract that off also. The next time we run n- 3 and we keep doing this all the way until we get to 1, right.

[00:07:30]
So if we sum all these numbers up the way to be able to sum this of course is via that formula that I showed you. And so that's how many literal steps we're going to take. And so there you go, we could replace this technically with n- 1, right, n- 1 multiplied by n- 1, plus 1, right?

[00:07:49]
I did a bad job. But again, yes, there's still gonna be an n squared somewhere in there, right? Like if you just use FOIL, you'll see that n squares eventually, there you go. You have it so, the actual real running time is n squared minus n over 2 and then break that all off because insignificant factors all that it's still n squared.

[00:08:08]
Does that make sense? So nothing really changes, I just tried to keep it pretty simple. All right, I think it's a good time to move forward, right? We've got one more question.
>> What's a good sorting algorithm for immutable arrays, I assume all allocations for Bubbles would be deadly.

[00:08:31]
>> Well, the thing is that if you create an immutable array, you have to come to it with the fundamental understanding that you are creating an exceptionally poor performing data structure. Immutability is supposed to come with the ease of use, but it comes at the cost of space and replicating space.

[00:08:50]
And so yes, it's big computers are extremely fast at mem copy, but that means you're doing an operations over and over again. So if you were to literally do that the worst case scenario is that you have a reverse sorted array and you try to bubble up that means every single time you did that you'd have to bubble which means you'd have to copy n.

[00:09:07]
So it'd be somewhere in the n cubed if not higher and I'd have to think about that but it'd be a very poorly performing algorithm. I also would never use immutability and sorting in the same sentence cuz that just seems like it's a terrible idea for performance.
>> You look chunk.

[00:09:22]
>> Yeah, your computer would chunk really hard.