OK.
So welcome back, everybody in this lecture, we're actually not going to introduce a new sort quite
yet and the subsequent lectures, we will talk about some new and better sorts.
Maybe just one, actually.
But in this lecture, we're going to focus on revising our bubble sort.
If you remember in the last lecture, we kind of talked about how the algorithm that we came up with
was, like extremely rudimentary.
It just had like a double, you know, a nested for loop where it tried to just do a full path of swapping
for as many elements as there were in the array.
And you know, that was all it.
Did it just check to see if something was bigger and it just kept swapping it and it just kept swapping.
And you know, eventually the whole array is going to be sorted because it does as many swaps as there
are items in the array.
It does as many full pass throughs of swaps as there are items, so as many pass through.
So that's the way that nested loop was pretty inefficient.
So we're doing a lot of redundant kind of pointless calculations in this.
So we're going to go through and kind of revise it a little bit.
So currently, this bubble sort of algorithm does a lot of these pointless calculations.
We're going to go ahead and step through and kind of see why and what's happening.
So let's go ahead and just walk through right off the bat.
We're going to start off on the left here and we know that we need to swap one in for it.
So we're going to swap one in for this is our first pass through.
We go over here, we don't need to swap four and seven because those are already in short order.
Then we go over to we're going to move over to the seven and three.
And those two are going to swap.
And so something important to think about is that on each pass through, essentially, we're going to
run into the largest value at some point inside of this array or vector.
And what we're going to do is we're going to bubble that largest value all the way to the end.
So even though we started with four right, we bubbled up before, but it couldn't really bubble up
past this point right here.
Seven is the largest thing, so we swapped it to here, even if there really had more like values in
it that were less than seven, like, I guess that would only be like two and five and six.
Then seven would continue bubbling up until it was at the end, so you can take that information and
make the assumption that on each full pass through of swapping.
We are going to take the biggest item and bubble it all the way to the end.
So the second pass through it will basically find the next biggest item.
So like the second biggest item and it's going to bubble of that all the way to the end and it's going
to stack up right against seven.
So that's like what's going to happen on the next pass through and then and we can see that.
So if we go here, we're going to not change one in four, but we are going to change four in three.
And so now we noticed that four stacks up against seven.
So the interesting thing is that when we continue doing this, you know, now we notice our whole array
happens to be sorted.
But we have this w we go and we check this again and then we're even checking this.
We're doing that third pass through now.
And on the third pass through, we are even checking these last two elements that we should know are
like totally going to be sorted because we've already done the first pass, which put the biggest element
on the end, bubbled it to the end.
We did a second pass, which puts the second biggest element, bubbled up and smashed up against the
seven now, which is the fourth.
So it's like piling up.
We do a third pass and even though we should know that we've already done two passes.
And that that means that the last two elements, the right most elements in the array of Vector should
be already handled and sorted.
We still venture over into this zone and we're redundant when comparing four and seven when we don't
need to.
So that is one problem.
Is that we don't need to be comparing this yet?
We are we're just looping all the way to the end.
This is the swapping the loop.
This is the inner loop, right?
Because we have our swap right here.
So this inner loop is considered that whole pass through each time.
Like, you know, I, we we do this many pass throughs.
And then this represents each pass through, so we did one pass through the seven, got to the end,
we did another pass through, the four got smashed up against the seven and we do another pass through
now.
And that's what we're currently on and there happens to be sorted.
So we know that we can potentially eliminate this redundant calculation when we're looking at stuff
that's already been sorted at the end.
But another thing that we can do is, I mean, look at this, the array is already sorted.
We should not have to look for a fourth time, right?
There's going to be there's four elements in here and this is and I go zero, I less than my size.
So that's going to be the zero one to three, which is four times.
We don't need to go through yet another time when this thing is already sorted.
So how could we handle fixing that kind of pointless calculation as well?
So we don't want to have to go through and do all the swaps again because they're pointless.
We could add a Boolean to do that.
We should check to see whether any swaps happen at all.
So think about this pass right here.
We're on the third pass through, right?
So if we go through and we didn't, we didn't swap it.
All right.
So here's the start of the third pass to one in three no swap three and four and no swap four and seven.
I mean, we shouldn't even be comparing four and seven.
That was another fix we just talked about, but four and seven, no swap.
There's no swaps at all if there's no swaps.
That means that nothing was out of order and therefore everything is in order.
So therefore no ray is sorted.
The victor is sorted.
So if the vector is sorted and we had no swaps, we should just stop the loop.
But how do we do that?
So let's go ahead to the code and try and fix it up, and let's go over how we could stop doing the
loop if we noticed that we did know swaps on one of the pass throughs.
So once the array is sorted, we should not continue trying to sort it.
So I'm going to go over here into them, and we're going to make some changes.
First off, let's change the first thing we talked about.
Why are we going all the way into this last two elements to look at them to swap every single time like
we should not be going up to that point?
We should only be going up to the point in which there are no sorted elements, right?
And think about it.
Stuff is getting piled up at the end here.
Right?
So.
Here we have four and seven each passed through.
We have one element that gets smashed up on the end, so first pass through seven, second pass through
four.
Now we don't need to look at this zone anymore.
We should look only up to here, right?
So how do we do that?
What is that, what is that position?
Well, the outer loop represents each pass through, right?
In the fact that we've done two pass throughs means that there are two things all the way to the right.
They have piled up that we do not need to look at.
So therefore our inner loop should stop.
Whatever point, you know, is less than how many items we have piled up at the end, so what does that
mean?
So whatever point, that's less than how many items we piled up at the end?
Well, we noticed that this loop has iterated twice for two pass throughs and we notice we have two
things at the end.
We know that this is the end of the array.
The size right.
This array is one, two, three, four or Vector, whatever you want to consider, this vector is one
two three four positions zero one two three position four would be out here.
We noticed that the size of the vector is four.
So if we do for.
Minus.
The amount of iterations that we've done, so let's say I is on.
So we've done it two times will be zero and one.
And then now we're on to right, because when the third passed through, so I will be two, so if we
are going to do four, minus two is two.
So we have a zero one two that puts us right here.
But we don't want to really be right here and look at the swap, we want to be one before that, right,
so that would be the size of the vector.
Minus two, minus one more in two, was I right?
So we want the size of the vector minus I whatever I wear on.
Minus one more, so that will put us in front of all the stuff that's piled up at the end.
So let's go ahead and put that into code.
So what we are going to do is say that Jay is not less than my exercise, but it's less than I'm going
to put this in parentheses.
My vector size minus I minus one because we want to go up to the point that stops before we enter that
piled up sordid portion on the right side.
So if this is a little confusing, just take a moment to kind of break it down.
Think of like, well, what is the size of the vector?
How many iterations of the outer loop have we gone through and what does that mean?
How does that relate to how many items have successfully been bubbled up to the end?
The big it's got bubbled up.
The second biggest got bubbled up, the third biggest got bubbled up and so on and so forth.
Each one of those first, second and third is representative of this outer loop.
This inner loop is just simply all of the swaps on each pass through.
So we want to stop trying to swap at the point in which we realize that we're about to enter that piled
up bubbled up portion that's already been sorted at the end of the era.
And that's where this comes in right here.
So now we have solved that issue.
So let's go ahead and verify that everything works, OK?
So I'm going to go ahead and say this.
Let me make sure I don't have too big of an array.
OK, it's just five.
So that's fine.
So I'm going to do it C++ and you've obviously that should be brought out.
So let's go ahead and run out, and we'll just go ahead and do, let's just say, six.
Four, seven, one three.
All right, so now we notice that this is sorted one three four six seven despite us entering it in
this order six four seven one three.
So that still works.
And even after adding our little small optimization to that, we noticed that everything is still sorting
correctly.
So what was the other thing?
Well, we talked about not having to do anything.
Once we realized that the array is fully sorted, we should stop, right?
We should not do a full other pass through.
We noticed here that everything is sorted and we're on our third pass through, but our loop.
Would go ahead and do another full pass through, right?
Because it's going four times and we've only gone three times, it's going to zero one to three.
You know, I have zero.
I one is two and three, that's four times.
We're only on our third pass through.
Yet the array is totally sorted.
We would have gone through here and been like, This doesn't need to be solved.
This doesn't need to be solved.
In fact, we're not going to do the last one anymore, are we, because we're stopping at the right
time?
So this doesn't need to be swapped and this doesn't need to be swapped?
And by that, I mean, like this and this and we stop here and we notice that, you know what, we didn't
do any swaps.
That means that this array is sorting.
This vector is sorted.
So how do we check that?
How do we check to see if we've done any swaps?
This is where we're doing a swap, right?
In this section right here.
How do we know when to stop the outer loop if we haven't done any swaps?
So what we're going to do is use a Boolean, and this is just the solution I'm going to do, so I'm
going to say Boolean.
I'll just call this swaps, or I could say, had swaps, so I could basically say had swaps equals false.
So I said it's a false in the beginning, assuming that there is no swaps, so we would just assume
that the array is sorted.
But if we do in fact do a swap, it means the array is not sort sorted.
And so if we do a swap, that means we're going to have to enter this if right here, right, because
this is a situation that calls for a swap.
And so we therefore do the swap right here.
Afterwards, I can say, had swaps.
I think that was what it was called.
Had swaps equals true because we did, in fact, do a swap if we made it to this code in the scope of
the if that means we did do a swap.
So I can set had swaps to true, which is kind of like turning it on and off switch, right?
The bullion.
We're going to assume that the array is sorted and this will tell us whether it's sorted or not.
Right.
So each time, though, we're probably going to want to reset this to be false, right?
So each time we go through, we're going to assume that it could be sorted each pass through.
We're going to say, Hey, this might be sorted.
So let's go ahead and do that, we'll say, had swaps equals false each time before we go through,
if we actually need to swap, we know that it's not completely sorted yet.
So it'll say has swaps equals true.
But then let's say that had swapped equals false.
We now go through a full pass through with this inner loop, right?
This will do a full pass through.
And we never do a swap.
Had swaps will remain false.
Right?
And the switch never got flipped.
If we never go in here, that means that we know that the array is sorted.
So at this point, we can put it if and we can say if we had swaps and actually what we want to do is
we could say if had swaps, of course, equals false.
But we can.
Also, just since it's a Boolean, we can just say if not had swaps, if it had no swaps, which means
swaps is false, right?
So if we not a false, it turns true.
This would be the same thing as just saying if had swaps equals equals false, which, you know, we're
sitting here.
So let's say we said it to false.
Here it goes.
In this inner loop, it tries to go a full pass through all the way through all the iterations of J.
Up to here.
And it never enters this.
If because everything is in sorted order, it gets down here.
And we're like, if had swaps, equals equals false.
If it's still is false, we never flipped the switch to true.
That means it's sorted so we can stop the outer loop at this point.
So this outer loop, we don't need to do this outer loop anymore.
So I'm saying, if not had swaps instead of saying if had swaps equals equals false and what are we
going to do?
What do we do?
If that's the case, how do we stop looping?
The only thing that we really know about so far is that the for loop just goes as long as we have set
a condition for it, right?
Like it goes this long as long as I is less than my vector size.
So it's just going to keep going and going.
Luckily, there is a special word we can use to break out of the loops to stop doing the loops and break
out, and it is called break.
So I just put the word break like this, and what that's going to do is it's going to break out of this
outer loop and it's no longer going to do any looping.
So we've finished the inner loop, right, and we come back out to the scope to this level.
So this level right here of the outer loop and then we're saying, OK, the array was sorted, it had
no swaps because this never got actually set to true.
So what we're going to do is break.
And when we see break, we're going to break out of whatever loop we are currently in, right at this
point, right here at this level.
Of brackets.
You know, we're in here, we're in this scope of the outer loop, so we're going to break out of this
loop here and stop.
Which is good, right?
We don't want to have to do another pointless pass through a series sorted.
So let's go ahead and make sure that our code runs with this.
So I'm going to go ahead and compile this.
And let's go ahead and run it.
So let's go ahead and just into something else, I say eight nine one four two.
There we go.
One two four eight nine So it looks like everything is sorted and it's good to go so we can also check.
It's good to check multiple kind of inputs.
Let's go ahead and make a bigger number here.
Let's just say 10.
Save this compiler again and again.
Let's say.
All right, so I repeated some elements, but we have zero one one three four five six seven eight nine.
So looks like this is working on this example as well, too.
So what we essentially did just to kind of recap was to get rid of that like non-essential next pass
through because at this point in time, we were on the third pass through.
So we pretty much went one pass through to pass through three pass through.
And then after this, we would have started back in the beginning for a fourth pass through, even though
one three four seven is already sorted.
So we got rid of that with the bullion.
And the other thing we got rid of is that we shouldn't be checking this with the question mark here,
right?
We should have pretty much stopped here before.
So we are stopping at this point right here.
So we're not doing these extra checks.
And what that will do is even if this was bigger, let's say we had four items piled up at the end.
We would stop before those four items, right, because we changed this.
Over to have this condition right here, so we're going as long as day is less than my vector size minus
I, because we want to kind of go back before all the piled up items and we're doing minus one to be
currently on the one before that, right?
So hopefully that is enough for you to understand how to make some small optimizations to bubble sort
and how to have a slightly more complex sort.
You know, the first thing that we did was like the most rudimentary possible sort you could ever do,
in my opinion, of course.
But now we have kind of just made these small little optimizations that will not necessarily make it
overall a better source compared to other sorts.
But it still makes it a better bubble sort.
All right, we have made our bubble sort of slightly more efficient in terms of certain cases where
it would stop early, you know, when it sees everything sorted.
It wouldn't do another pass through.
OK, so with that, I'm going to end this lecture, and in the next lecture, we will actually start
on another type of sort.