Four Semesters of Computer Science in 5 Hours Exercise 3 Solution
This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Exercise 3 Solution" Lesson
>> Brian Holt: So let's take a look at bigocheatsheet.com real quick. This is super useful if you want to see what the big O of everything is or if you can't remember like I can't half the time. So, so far we've done insertion sort and bubble sort. And you can see that they have a good best case scenarios.
[00:00:24] End squared average and end squared worst case scenarios which is not necessarily great. But they have constant space complexity which for the most part means you are you're sorting the array itself without it creating new arrays in the middle. Which means that that's constant time for spatial complexity, which ends up being a really good thing if you have a very memory constrained device that you're working on, for example.
[00:00:52] I can think of a great example working on the PS3 at Netflix. The PS3 is a great Interesting device but it has very memory constrained. And so if we have 10,000 movies that we need to soar, for example, on your PS3 we would probably not use something that's needs a lot of extra space, right.
[00:01:09] We might select something because it has a better spatial complexity, for example. Yeah, so that's just an aside something can refer to later really useful. So, all right, so let's talk a little bit about insertions sort.
>> Brian Holt: Let's make this smaller.
>> Brian Holt: Okay, so create a new function called insertionSort.
>> Brian Holt: It's gonna take in some numbers, okay. And then it's gonna have two nested for loops, right? And we're gonna do for. And then we're gonna start with with 1, because remember, we don't necessarily need to do the 0 element, right? Because the 0 element's already sorted, you already have a sorted list of 1, so we can go ahead and short circuit that and go to the next one.
[00:02:07] Okay, I'm gonna say i is less than nums.length.
>> Brian Holt: And then we're gonna do i++.
>> Brian Holt: Right, okay? Now we're gonna loop over every number in the array. Now we're going to do that inner loop that goes over the, just the sorted part of the array, okay. So we're gonna say for let j=0, because j, it can be the zero with element.
[00:02:40] So if we have a number that's the smallest element in the array it can go to the zero spot, so that's how we're gonna start that, with a zero. And we're gonna say j < i, right? I'm gonna do j++, right? j < i, meaning we're only gonna go over the first part of the array, not necessarily, we don't need to worry about the second part of the array at this particular moment in time.
[00:03:07] Okay we're gonna cost snapshot again, just so we can see what our sort looks like.
>> Brian Holt: And then here we're just gonna ask is nums i < nums J, so nums i is going to be that item right outside the list, right outside of our sorted par and nums j is going to be where we are looking in our sorted part of the list.
>> Speaker 2: Yes we have a question about ES6 from JC.
>> Brian Holt: Sure.
>> Speaker 2: Does let in ES6 infer i as a variable in a for loop? Is that why we didn't have to type?
>> Brian Holt: No, that's a mistake.
>> Speaker 2: [LAUGH]
>> Brian Holt: In fact you can see down here it was yelling at me right there.
>> Speaker 2: Okay.
>> Brian Holt: Yeah let i = 1, thank you.
>> Brian Holt: That would be a neat feature though kind of confusing though, so maybe not. Okay, so now we're going to ask is the number that we're looking at is that, should that be unsorted when we're looking at this very moment in time, right.
[00:04:17] And if it is then all we're going to do is we're going to pull that number out and we're just going to insert it in. So what we're gonna do is,
>> Brian Holt: I guess we can use const here, yeah. So const spliced equals nums.splice (i, 1). Splice and slice, I get those mixed up all the time.
[00:04:43] I don't know if anyone else does, I do personally. I have to look up the MDN every single time I use splice or slice to remember which one does which. And splice is the one that's actually going to take it out of the array. It's a destructive method that it actually does modify the array that it's on.
[00:05:00] And it's going to i and we're going to take out one element right, that's what splice does. So it's going to take out a list of one, so if I did two here it would take out two things right, but we're just going to take out one. And then we're gonna do splice again.
[00:05:19] We're gonna do nums.splice(j) so we're going to be inserting it at j. We're not gonna take anything out, that's what the 0 means and then we're going to, come on. We're going to insert what we got from spliced. Remember a splice is an array we actually have to take the zero with element of Splice.
[00:05:44] Right so the first line takes something out at index i and second line is insert something at that particular spot in the array. Does that makes sense? Okay, question?
>> Speaker 2: Yeah from Damion, you just now give a visual a visualization only of the array before and after are different?
>> Brian Holt: Yes so it de-duplicates, just because otherwise we would have a whole lot of arrays looking exactly the same which I found very interesting.
>> Brian Holt: Great, and like that I think that's the the end that should do it.
>> Brian Holt: And look we are passing right. So if you remember our bubble sort we called Snapshot 101 times right.
[00:06:39] This time only calling it 45 times. So again that's a, it's not an order of magnitude, but it is a pretty nice coefficient to only do half the amount of work that we were doing before. And again you can look here. So we started with an assorted array of 10, then we insert five, then we insert three, and then we insert eight, and then we insert two?
[00:07:04] Yeah, then we insert two,so on and so forth, right. So that's how insertion work is working, it's looping over and just inserting one element at a time in its correct place. And everything before 10is sorted, right, in this particular one right here. So this is 2, 3, 5, 8, 10, and everything after is an unsorted unknown mess.
>> Brian Holt: Any questions about that, does that make sense?
>> Brian Holt: See blank stares. [LAUGH] Glassy eyed stares. Again, this is difficult, right. So don't feel too bad if this feels difficult. It's something that you should go over a couple times to make sure that you feel good about it.