Bubble Sort Practice

[00:00:00]
>> I'm gonna give you some time to try and implement bubble sort yourself. So, should be able to click on here if, I think mine I actually have it open here. So Come back here to our code sandbox. And I want you to work on bubble sort.test. And you can go ahead and delete the .skip here.

[00:00:40]
And you can go ahead and get started on that. You can look here at the test. You can call it right here, or you can write all the code here. As you can see here, I now have one failed test. Now, and actually I'll show you how to do this when we get back after you try this, but there's a cool little thing I added here that you can visualize your sorting happening as well as it goes on.

[00:01:07]
And I'll show you how to do this when you get back but if you wannna give it a shot right now, you'll put your bubble sort code here in sort. And then anytime that you wanna take a snapshot of the array, which basically means that the beginning of every 4 loop.

[00:01:22]
It'll actually visualize you over time of how your bubble sort's working, which is kinda cool. But I would say do it here, for us to do it here in the bubble sort here. Again, let's actually do that first as well. In fact, I might just commit that. Well, stay on page.

[00:01:48]
If you wanna get rid of all the console stuff here, it's under pathfinding and under the solution and you just need to log out or remove the log maze parts. But I'll do that here in just a second. So just another kind of pro tip here as you're doing your code sandboxes.

[00:02:23]
I tend to leave these skips on here. Let's do the test out skip until I'm fairly certain that I have at least a good first shot. It's really easy to get infinite loops, if you're just letting it run. In fact, I think code sandbox lets you yeah, actually, let me show you that as well, that's probably a useful thing here as well.

[00:02:46]
This little blue circle up here, this toggle file watching, it'll actually just run your code as you're typing which is kinda slow. So if you just click on that. It won't try and run it every single time that you type, which is probably a good thing, especially when you get into recursion, you can actually crash your browser.

[00:03:07]
Another kinda pro tip here is if you've created your own code sandbox account, you can just save the file before you try running it, so that if it does crash, you don't lose all your work. Also, don't refresh the page. I probably should have told you all this maybe a bit sooner but now you know, coz if you refresh the page, it's gonna drop all of your changes as well.

[00:03:30]
Okay. So first thing here, is we wanna do create a variable called swapped. We'll set that equal to false. This is just gonna be the, I think the term for is the sentinel variable. That as soon as we swap anything in the array, that means we have to do another loop, okay?

[00:03:51]
Here you can do a while loop, but I never get to use do loops and whenever I get to use a do loop, I feel like I must because I never otherwise use them. So I'm gonna say do which is very similar to a while loop. What's the difference between a do loop and a while loop?

[00:04:09]
Well, a do loop always happens at least once, which in this case, you always wanna least check if it's sorted or not, okay? So I have this do loop here. And I'm going to say, on the first thing, swapped equals false. That's the first thing at the beginning of every single array, we're going to assume that nothing has been swapped, and then we're going to, if something does get swapped, then we will set swap to true which will cause it to loop again.

[00:04:40]
When I say 4, let i equals zero. I as less than num style length i++, okay? And then in here, we're going to say if numbs of i is greater than nums of i + 1 Then we're gonna swap the numbers const temp equals nums i, you could write some function that does this as well, it's up to you.

[00:05:21]
Nums i equals nums of i + 1. Nums of i plus 1 = temp, and swapped = true. It's basically it right there. There are a number of things here that I could do that could speed this up. For sure, I tried to write just the simplest code possible for you all to understand this.

[00:06:04]
But a really good exercise for you to do later is to go and actually, like, for example, I could track how many iterations I've been through, right? And I could have like const iterations and are actually have to be alette. And that could do a ++ at the end of every loop here and then I could say minus iterations right?

[00:06:24]
And that would Allow me to do less than less loop throughs, I think that could actually make this even minus one. I think that actually does work. But let's actually try and see if this actually works as it Is, And we'll click play. Yeah, I got to return this at the end.

[00:06:50]
Yeah, thank you. All right, so let's try that again. Sometimes it gets unhappy of That should be working. But let's go ahead and go take a look at the solution just to make sure here. Yeah, and you can see here I mean, that's basically the code that I wrote right there.

[00:07:22]
If you are seeing that where it doesn't do that, what I would do is I would just save, refresh the entire thing cuz again, code sandbox can find itself in a bad state. So, the next thing I kinda wanna show you here, Is, let's just go ahead and refresh this.

[00:08:00]
Bubble sort, you running now? Yeah, there we go. Now it is running. Cool. All right, so let's do some fun little visualization here. I'm just gonna copy the body of bubble sort here, and then I can have this thing under source called sort.js. You can actually just come in here and paste this.

[00:08:26]
And I'm gonna uncomment these snapshots right here. And let's just call this nums. All right, so now if I go over here and browser, Okay? And then they come in here into sort, you can actually visualize what's going on here. So the one thing this will do for you is actually do duplicates for you, so as long as you just, so if I call snapshot multiple times in a row with the same array, it'll cut it out so you can only see what happens when it swaps.

[00:08:59]
So you can see I took 71 snapshots by putting a snapshot here and then one of the ends just to get the final product. And it actually only got 22 unique snapshots. But you can see here, the nine bubbles up, the eight bubbles up the seven bubbles up, right?

[00:09:18]
And you can kind of see that bubble sort kinda working over time. Or I mean, we can do make this even bigger. This will be pretty ineffective. You can see I kinda made it unhappy cuz this is what happens when you use n squared algorithms. I've actually locked up my browser.

[00:09:46]
That's how inefficient this this sword is. There we go. It's also a lot of react rendering. You can see here this took almost 9000 snapshots. And it has to have 2555 unique snapshots. You can see here the 97 bubbles up until it finds 100, then it finds 99, that's gonna bubble up until it finds 100 99 actually is the biggest cuz it's going from that to 100.

[00:10:20]
You can look how long this this rendering is. But it's kinda pretty to watch all the colors kinda come together, right? Anyway, I think it's cool.
>> In the f check there, are you intentionally going out of bounds and relying on a number greater than undefined will be false?

[00:10:41]
>> Yeah, so the question is here on line 13. This obviously at some point is going to go out of bounds and it just ends up working okay, so I just never bothered fixing it coz really only pops to go outside the array once and it doesn't. But you totally could say and no, this is gonna try and re render again.

[00:11:08]
>> You could just start the for loop from i = 1 and do the check with i and i- 1.
>> Yep, there's a lot of ways you could handle that and that would totally be fine as well. So anyway, I found this kinda fun. Feel free to to play around with this.

[00:11:24]
This will work for all of the basically non recursive sorts. So this will work with like the radix sort. This will work with selection or insertion, all those sorts.