OK.
Welcome back to another listen, everybody in this listen, we are going to be going over insertion
sort, so this is a new sort and it is kind of like a bubble sword, not too much more complex.
But the reason I'm introducing it is just because I think it's important for us to look to at least
at a couple of swords.
So I gave you that challenge to kind of come up with your own sort.
But this will kind of expose you to other ideas that other people had to solve this sorting problem.
And it's important for us to kind of look into these different things as well just to kind of intellectually
challenge ourselves because we're getting into a portion of the course where we're needing to like manipulate
data more.
You know, the sorting challenge is kind of a an interesting one because we have to really focus on
the values of things and think about the fastest way or most efficient way that we could get those into
the right order.
And so.
There's some really cool sorting algorithms out there.
The two kind of most renowned ones that performed the best in terms of efficiency are merge sort and
quick sort.
Those are kind of the de facto ones that people use for sorting because they are quite fast.
I'm not going to get into this at this point in the course because they kind of sometimes rely on this
concept that we haven't gone over, but that we're going to go over in the algorithms and data structures
section.
So I don't want to go over those quite yet.
But if you would like to look into those like merge sort, it might be a good one.
That one is a lot more efficient than both this insertion sort and bubble sort, so that could be a
cool one to check out.
But I felt like it was a little bit too confusing for this part of the course.
So if you like, checked out in the hour and welcome to you and I'm going to go over another pretty
basic sort, it's just slightly more complex than bubble sort, but not really.
So let's go ahead and get into it.
So insertion sort is kind of doing the opposite of bubbling remember bubbling with us and moving stuff
from the left to the right, and it was kind of piling up one by one at the end here.
But the goal of insertions or is to pull a new element into a left most sorted portion of the array
and keep doing that until the end of the array of vectors reached.
So let's just pretend that we start here on the left, which we don't, and that's what we're going
to do.
But what we want to do is say, OK, whatever to the right of me.
Can I insert that into here?
Is it like less then than this?
If so, then what I can do is bring it in and then keep moving it until it's in the right position.
And we're going to keep track of the sorted portion of the array, and I'll color that in green.
So let's go ahead and start.
So what we're going to do right off the bat is look at this first item eight and the item right after
it.
Three.
And we noticed that what we can do is swap those to you because three is less than eight.
So that's what we do and what we do now is we're going to consider this portion of the array as sorted
because we have done this swap.
When we start off, we just consider this as sorted.
But now, since we've kind of swapped it, we're going to move to the next square here and we're going
to consider that sorted.
So I didn't market green in the beginning, but we can kind of think of this as being sorted.
It just has the number eight eight one number by itself is sorted.
So I didn't really want to show until we got to two.
But now that we've swapped it, we have now moved over to here and now we are considering this square
and we can say that since these two swap, this is sorted right?
Three comes before eight.
This section right here is a sorted portion of the whole array.
So what we are doing is we are moving this way.
And each time that we move one this way, we're trying to see if we can take this thing, the next thing
in the gray area and move it into the green area if as long as it's less, and then we're just going
to continue moving it through the green area until it arrives in the right position.
So in this next instance, we're going to try and take two and see if it can be moved into the green
area, which is sorted.
And then we're going to make sure that we keep moving to to the left until it's at the right position.
So you can already kind of think of this in terms of code you might be realizing, OK, well, we kind
of have this one repeated thing of moving to the right and for every time that we move on to the right,
we are going to potentially take an item and move it to the left a bunch.
So think about that.
We'll be getting into the code, of course, after we go over this theoretical portion, but now what
we're doing, of course, like I said, is comparing two to eight is to less than eight.
Yes, it is.
So we can put it into the green area.
So we swap these two, actually.
And then so what we're going to do is now see if we can move to further through the green area, which
we can write to is less than three as well, so we can swap two over.
And now we're going to consider all of these three to be a small portion.
So we're going to move over to the square now.
So this is all sorted here.
What we're going to do next now is see if we can move nine into the green area.
Nine is not less than eight, though, so we're not going to move nine into that area.
So we're going to move over.
This is all sorted, right?
Two three eight nine.
Now we're going to see if we can move forward to the green area.
As for less than nine, well, yes, it is, so we can move it in there.
And now our job is to make sure that we move for into its correct position.
So is for less than eight years.
So swap.
Let's go.
Here it is for less than three.
No, it's not.
So leave that.
And then now we move over another square, but we're at the last square, so we're pretty much done.
Their whole array is sorted, so we have two three four eight nine.
OK, so now I'm going to head over to the editor to do some code for this, so I'm going to go over
to them.
You can head over to whatever editor you would like.
But I've kind of already made a file here, and I've included I stream Vector using a namespace and
I made a main function, so I'm going to go ahead and make a vector just like we did for bubble sort.
So I'm going to call it a vector type and animate part my vector.
I'm also going to make an ant called my end so we can read into it just like we did with bubble sort.
I will want to make attempts so I can do swaps.
And then another two variables that I'm going to want to make is a variable for the actual item that
we're going to try and moved into the storage portion.
So an item that needs to be inserted from the gray section into the green section, right?
So that next box, let's say we're on the lake, right?
Most green box, so I can bring up the graphic here again.
Let's say that we're here and we want to look to see if we can take this great item and insert in here.
So this gray box, whatever stored here, which is nine, that is what we're going to consider for our
variable to be inserted.
So I'm going to make an integer variable for that.
And then another thing I want to do is keep track of the positions in the green.
So as we're moving to the left through the sorted portion, I want to have a variable to keep track
of that.
And why do I want to do that?
Well, I think I'm going to use a while loop to be able to handle that because I want to keep swapping
to the left.
As long as the, you know, number that I'm considering is less than the number, the next number to
the left.
So I want that's a condition, right?
And then I also want to make sure that I don't go off the end.
So I don't want it to be zero so that I have to be another condition with that kind of calls for two
variables, right?
A variable for the inserted, the item that needs to be inserted into the green portion and then another
variable that keeps track of whatever position we're on in that green portion.
So I'm going to say like an insertion item and then I'll say, and this will just be sorted position.
So what I'm going to do now is just make a for loop.
In fact, I'm just going to start out with like that standard like five, we're going to have like something.
They ask the user to enter five numbers, just like we started out with with bubble sort, so I'm just
going to do that so we can have some continuity here.
So I'll go ahead and print out, just enter a number and then I'll scan into that in the end.
And then what I want to do is I want to push back to my vector, right?
So I want to push back my end to the vector.
Then now comes the part for sorting, so let's see or do so with the insertion stored portion.
So we got to think about the fact that we're doing kind of two processes, right?
So we're moving one to the right through the whole array, and that's us trying to make, you know,
increase the sorted portion.
So it's like move to the right one and now put a green box there, moved to the right one and put a
green box there.
And that's like us increasing the size of the green screen portion, right?
So that's going to be an outer loop for us.
So I'm going to say four and I equals and I equals zero.
I less than my vector size I plus plus.
And then what I want to do in here is I want to make sure to set that variable that we're currently
considering to be inserted, right?
So I have this insertion item, and what I'm going to do is say insertion item equals the current item
that I am on right now.
So I'm going to call that my effect.
I.
So we're just going to consider that we move over to like some gray box, right?
And then we're going to consider moving that item in that gray box to the left into the green portion.
So I also want to keep track of the position for that green portion.
So what I'm going to do them is a sorted position.
Oops.
Sorry, position is equal to I minus one, right?
Because we want to be one to the left of where we are.
So let's go ahead and think about this.
So what if we were here?
This is going to be I.
And so we are interested in whatever is there at.
I write my vector is the insertion item.
So in this case, it would be nine.
This is our insertion item.
But then our position that we want to start out with to consider for the green portion is one less right,
one less right here.
One position less is the start of the green portion and we're going to be moving this way through the
green portion.
All right.
So that's why I'm saying sort of position equals I minus one.
So we're going to start out there and then we need to move left.
So since we're going to move left, what I'm going to do is use another loop, but I'm going to use
a while loop because I want it to be based on a condition.
So I'm going to say while and this is going to be well sorted, position is greater than or equal to
zero because I don't want to go off the end, right?
Like if I don't want to go here, here, here and then I'm at zero and then I keep trying going.
So I keep keep trying to move to the left.
I don't want to do that.
So I'm going to make sure that I have that.
And I must say, how long or what's the condition that we keep?
We keep wanting to move through it, right?
It's whether we're swapping like these items or not, right, so.
Go ahead and present this, so we're swapping like B for over, right?
So we had a for here.
We move the floor into the sordid portion and then what do we do?
So now we're in our while loop.
So what we want to do is keep moving to the left.
As long as this thing right here is less than this thing right here, right?
So what is that going to be?
Well, it's going to be as long as my vet sorted position.
Is greater than.
So that means that the thing that we're on in here, so like eight or something like that, as long
as this is greater than what was four, well, four was actually our original insertion item here,
right?
So we wanted to take four.
We inserted it into here, right?
That's what we want to do.
So this is our insertion item, right?
So we're wanting to compare the thing to the left.
To this insertion item.
So that's what we're going to do, remember, these sordid position starts off one to the left.
So just to kind of show again, it's going to be right here.
So this is sort of position, right?
Just this box.
It's not nine.
It's just this box.
My vet index sort of position is the nine.
So we're doing that, and we're wanting to compare it to the insertion item, right, the insertion
item is this fall right here in this example.
So as long as that and my vague sort of position is greater than my insertion item, then I want to
keep moving to the left.
And also, of course, as long as the sorted position is greater than or equal to zero, we do not want
to go off the left end of the array or vector right.
So what do we do now?
Well, we're just going to keep swapping it through, right?
So let's go ahead and use our tent.
This is just us doing that similar swap code that we used for bubble sort.
So I'm going to say temp equals my vet sorted position Exposicion.
And then I'm going to say my vet storage position equals my vet sorted post this position plus one because
I want the thing to the right of it to now be swapped into the current position mine.
And since I made this temporary here, I can now say that my vague sort of position plus one should
be temp so I can actually go over and just copy this, yank this and paste this here.
So this is just code that you should be familiar with is similar to what we did in bubble soy.
So it's just making attempts so we can hold this original value of my exalted position.
And then we take the thing to the right and put it into where we're currently at in the vector.
And then since we already have overwritten that, thankfully we saved it.
We can say now the thing the position to the right should hold the temp that we saved.
All right.
So after swapping, all we have to do since we're in this wow loop is, of course, update our sort
of position, right?
Because we now need to move to the left again.
So all I'm going to do is, say sorted position minus minus so I can move one to the left, and that's
really all there is to it.
This outer loop is to keep moving the through the array originally with increasing our sorted portion
by one each time, right?
And then we grab our insertion item, the thing that we want to put into that sordid portion and then
we say, well, the start of the sordid portion is going to be wherever we're at for that insertion
item minus one minus one.
And then what we're going to do is say, OK, let's start.
It loops to move something through this sort of position as long as it's greater.
Of course, we don't want to even move it into the sort of position if it's not greater than it, right?
Sorry.
I mean, less than as long as the insertion item is less than that first position in the green portion.
And then we just keep swapping it to the left through the green portion, right?
And that's what this loop is doing right here.
It's just a simple swap and then minus minus and then swap and then minus minus.
And just keeps doing that until it gets to the very beginning of the array or whether it's in the right
position because it's no longer wherever we're at is no longer greater than our insertion item, right?
So all you got to do now is, of course, print it out to verify that it works.
So I'm going to say that it was zero, just kind of have the same loop again.
I have less than five plus plus and I'll go into here and I'm just going to say, see out my vet I and
then I'll put some spaces here.
And then, of course, I think I'll do a little end line here.
All right.
So this is just say like print out the whole piece or the vector.
And yeah, this is our insertion.
So let's just label some of this stuff.
So they sent me an item to be inserted into some sort in an area.
This is just,
let's say that the right most edition of sorted area.
And then here is us doing our loop.
So this is like our walking loop.
And then we, of course, do the swap.
And then let's just say this is move our process in one two to the left and inside story area.
So you some comments that kind of can explain it better.
Right.
So the outer loop this is this is just an assertion.
So it starts here.
Set the item to be inserted into the sorted area, set the right mouse position of the storage area.
So that's the right mouse green box.
Now we go into this swapping loop where we're going to move through our sorted area.
So here's the actual swap these three lines here.
And then this is just to move one position to the left inside that green sort of area.
And then we go back up here and check the conditions and continue if we need to.
And then now we're turning out that whole thing.
So let's go ahead and compile this, and I say so sorry, I'm saying, Paul, this idea out.
Uh, my sordid position was not declared in this, I just spelled that wrong.
I forgot to put the I, so go ahead and fix that.
Sorry about that.
So it's like here it was a.
Misspell air, hopefully you don't have any more.
OK, that looks good, so let's go ahead and run this.
So interior, no, let's just say.
Or nine one three six.
And then we go one three four six nine.
That looks to be in Soviet order.
Let's go ahead and try a bigger example, just like we did before with bubble sauce.
So I'll go ahead and increase this to like 10, and then I'll go down here and increase this to 10.
So let's go ahead and compile that and run this, so.
All right.
So let's see, one two, three five, seven, eight, nine, 11, 22, 44, it looks like that is in
good, solid order as well.
OK, so that's pretty much all I have to go over with insertion sort.
Like I said, the reason that I introduced this was just to kind of give you another example of sorting
and the like show you that there are multiple ways that you can solve the same problem, and that's
going to be a really important thing as we move forward.
You know, everyone might be coming up with their unique solution.
And then eventually, when we get into the algorithms portion of the course, we're going to look at
not only just coming up with a way to solve the problem, our own way of solving the problem.
But we're going to compare different ways to solve the problem, to make sure that we can do it in the
most efficient manner.
Right.
We're going to look at not only solving the problem, but kind of optimizing it, making it more efficient.
All right.
So with that, I will see you in the next lecture.