Four Semesters of Computer Science in 5 Hours Exercise 2 Solution

Transcript from the "Exercise 2 Solution" Lesson

[00:00:00]
>> [MUSIC]

[00:00:03]
>> Brian Holt: Something I wanted to mention to everyone is that if you're not getting these exercises the first time that's okay. This is definitely the fire hose that you're drinking from here. And just remember that college students have two years to get through all this stuff and we're shoving this down at you all in one day so it's tough, right?

[00:00:24] This is something that you should do and then redo and then redo again until eventually that repetition hopefully will make sense in your head. Okay, so let's talk about bubble sort. Excuse me. So we're gonna create a bubble sort function.
>> Brian Holt: So again this is just arrow function.

[00:00:52] You could rewrite this as function bubble sort and that would be just fine too, okay? And then so we're gonna have an outer loop that's gonna keep track of if something was swapped or not, okay? So we're gonna have, let swapped = false, right? And then every time something swaps we're gonna set false or swapped equals to true, okay?

[00:01:16] Here we're going to do our do loop, so do, okay? And then we're gonna input in, okay. The other thing is changes to x describe by the way if you haven't already done that. Okay, and then we're gonna do a while here. So while something has been swapped we're gonna keep doing this.

[00:01:40]
>> Brian Holt: And then inside of that we're going to do with this inner for loop, right? So for (let i = 0) i is < nums.length;
>> Brian Holt: i++. Another thing that bears mentioning here is you can make these more efficient. Right now I'm going for readability cuz we're not going for the ultimate let's make this as fast as we can right now.

[00:02:11] We're going more for understanding. And the reason why I bring that up right now is really what you could do is you could do l = nuns.length, right? And then i is less than l. That's faster and is more efficient, but what I'm trying to demonstrate is we're not going after these micro optimizations, right now, right?

[00:02:31] We're just going for the broad strokes here I just think that's more readable so we're sticking with that, so deal with it. Okay, so we wanna use our fancy visualization thing. So we're just gonna call snapshot right here.
>> Brian Holt: Okay? Again non-essential, right? We're just doing this so we can eventually see what we're doing.

[00:02:55] So if the number that I'm on right now, i, is greater than i + 1, right? So if it's bigger than the one next to it, then you're gonna swap them.
>> Brian Holt: And here it's gonna write a really simple swapping, right? So we're gonna say
>> Brian Holt: Grab a temporary one so it's gonna say this gonna be nums[i] nums[i] is going to be equal to nums[i] + 1,

[00:03:37]
>> Brian Holt: And nums[i] + 1 = temp, right? And then here we're gonna say swap is true, right? Because we did do a swap here, right?
>> Brian Holt: And down this is again not essential I'm just gonna call snapshot again so we get the final way that the array looks.

[00:03:59] I think otherwise we won't miss it, okay? So, let's go take our extra scribe off. And I might have gotten an infinite loop
>> Brian Holt: So if you see something like this happen where your browser totally seizes up, it probably means that you have infinite loops somewhere.
>> Speaker 2: You can set the div swap back to false.

[00:04:32]
>> Brian Holt: That's right. You have to do it, that is totally right. Why did I not put that in my notes? That's why, okay, so this is what happens. So don't be ashamed because I obviously just did it. Anyway we'll just go look at the answer after I done it all again

[00:05:00]
>> Brian Holt: Right, so I forgot to do this, right, good point. Because if you don't set it to false then it's gonna true and is going to keep running forever. So these are the kind of problems you run in writing algorithms. Lots of just broken crap everywhere.
>> Brian Holt: Okay?

[00:05:19] This is look for pretty much the same though.
>> Brian Holt: So again, we're looking at this blow that up a little bit.
>> Brian Holt: Notice that you see ten just kind of bubbles to the top, right? And then 9 is right there so it kind of bubbles to the top and if you look at 8 here, right?

[00:05:43] Eventually 8 is gonna start bubbling to the top. You look at 7, that one starts bubbling. 6 and things just kind of start slowly slipping into place, right. Bubbling, right? Bubble sort. Great, any questions about that? Feeling pretty good about that? All right cool, I see mostly head nods.

[00:06:06] So I can only assume that I nailed it, all right.
>> Brian Holt: So you just did your first sorting algorithm, congratulations. They only get harder. [LAUGH] Okay, Big O on this, right? I think we talked about this it's going to be n squared and it's gonna be a really bad n squared because you're gonna be looping through a lot there's a lot of a wasted effort in here, right?

[00:06:33] You'll find a lot with algorithms that you're trying section things off if I can say this part of the array is definitely sorted out that I can make assumptions I don't have to sort it again, right? And so you can start ignoring parts of your array. And that's kind of what we're gonna get into is we're gonna start ignoring bigger and bigger pieces of our array