Insertion Sort Practice

[00:00:00]
>> So let's go ahead and give insertion sort of shot, you're gonna hear edit on code sandbox. We're gonna pop over to Insertion-sort. Can you ignore that part? So you'll have the test.skip here again, make sure you delete that and write your code. And your code is gonna go here into insertion sort, and yeah, go ahead and get started.

[00:00:32]
So we're gonna pop into here, this is InsertionSort.test.js. And we're gonna have two for loops here. We have an outer one that's gonna loop over the array, starting with the first element in the array, right? Cuz the zeroeth element will be the sorted part of the array. [COUGH] And then we're gonna go inner loop that's going to go over backwards to find out where it should go.

[00:01:05]
So we're gonna say for, let i = 1, i is less than nums.length, i++. And I'm gonna turn this off autorun, soft tab, okay? Then I will say let numberToInsert, so this gonna be like the number that we're gonna be comparing, = numbs(i). Then we're gonna say let j, cuz we're gonna keep track of that number as well.

[00:01:52]
Here, we're gonna say for let j= or let's put just j, j = i- 1, nums(j) is greater than numberToInsert and j is greater than or equal to 0. And then at the end of every loop, we're gonna do j- -. Now again, there are multiple ways you can totally write this, this is just the way that I chose to do it.

[00:02:26]
But here we're starting with j being 1 below the number that we're trying to insert. And then we're asking, is the number at that point, is that greater than number to insert? And is it greater than 0? And if not, then we're gonna just move the number to the side, right?

[00:02:53]
So we're gonna say nums(j + 1), Is gonna be equal to nums j, so this is actually moving the numbers backwards in the array. As soon as that's true, then we've arrived at the point that the number is ready to be inserted. So we're gonna say nums(j + 1) = numberToInsert.

[00:03:25]
And again, if you arrive on the number where it's already in its correct place, this is just going to assign a number to itself, which is totally fine, no problems whatsoever. And then at the bottom, we just say return nums. That's it. So the outer loop which is going forward from assuming everything behind it, everything underneath i is going to be the sorted part of the array.

[00:03:54]
And then we're gonna have j, which is going to work backwards through the sort of part of the array to us insert the next thing. So in theory, we should be able to put remove test.skip down there and run our tests. And hopefully, if we get into insertion sort, it looks like we are passing there.

[00:04:14]
Pretty cool. So let's just go visualize that for funsies. Insert that, we're gonna pop over to sort here. And where are we gonna snapshot? We wanna snapshot, Probably every time at the end of this, right? Now this isn't truly ten comparisons going on. But you can kinda see here that you have here at the beginning of this, we can also snapshot beginning as well, just so we can see where we start.

[00:05:10]
Snapshot numbs, So you can see here this three right now represents kind of the sorted part list. 2 gets inserted before the 0 at the beginning, and then A gets inserted the right place, then 5, right? And so you can kind of see that insertion going on until eventually down here, we end up with something that's sorted.

[00:05:33]
Or we can do this for 50 or something like that to see something a little bigger. But you can kind of see this blue demarcate the sorted part of the list from the unsorted part, right? So everything before this 49 right here in this particular row, that's all sorted, 3, 4, 6, 7, 8, 16, and then everything after that is the unsorted part.

[00:06:06]
Pretty cool, right? And then down here at the bottom, you can see we end up with a fully sorted list. The idea is that you are moving numbers forward in the array, so 40 gets moved to 8. Let's just make this bigger and let's make it smaller. So here, let's look at this line down here, the 0, 3, 4, 6, 7, 8, 9, right?

[00:06:41]
So, we have 2's that's gonna be the next number inserted into the unsorted part of the array. Everything 9 to 0 here, this is sorted. What it's gonna do on these iterations, in fact, let's just visualize that, I think this would work. We just say this is gonna get a lot bigger but snapshot(nums).

[00:07:14]
So you can kind of see here now we start having these redundant numbers, right, like 8 here. It's moving piece by piece the array forward until eventually we create the correct space. The down here after this for loop, kind of get rid of this, and move this over a little bit.

[00:07:33]
So that this is moving everything forward 1, right, so 8 moves to here, then it moves to here, then here, then here, right? Until eventually, we arrive to this part of the code right here, line 18, which is actually just going to insert that number into the exact correct place.

[00:07:51]
Does that make sense? So that's the actual part of the code that's moving numbers forward until you create the space where we're going to insert our new number. Hopefully, that makes sense. It's kind of abstract. It's better if I put it here. Yeah, again, you can see these numbers kind of where they're duplicated and they're moving, right?

[00:08:25]
So here, we've moved 5, 4, the number we're trying to insert right now is what? 9? Or something like that? We've kind of pulled that number out of the array and we're waiting to insert that. That number is being held here in number to insert and it's actually not being reflected in the array.

[00:08:46]
That's why you see the duplication, until eventually we rereinserts that number here on line 18. Cool. I feel good about that explanation. [LAUGH]