In our previous lecture, we got an overview on what bubble sort is and how it works.
So now that we have a good understanding of how Bubbles sort works, we can begin implementing our own
solution for that algorithm.
So the first thing I want to do is create a new function called bubble sort, and it's going to look
very similar to what we did for selection.
So we're going to create a bubble sort function and we're going to pass in a mutable reference to a
vector that's also going to return a vector.
And then down here, I want to go ahead and create some of our test cases.
So we will say let mute vec
equals vec.
And then in here I want to mimic our test cases that we did in the previous lecture.
So we did
a5411132
and then we also did
a.
Five one, four, two and eight.
So now in here, we know that we are going to run bubble sort and we're going to pass in a mutable reference
to our VEC.
And then we know that we're going to want to print it out to make sure that our vector was properly
sorted.
And we'll stop there for now.
That way we can make sure that this at least works before we continue down here.
So now up here in the function, we're going to start implementing in our algorithm so we know that
we're going to need to for loops.
So we'll go ahead and create our first for loop and we'll say four I and one to the array dot length
minus one.
And since we knew we know from the previous lecture that we actually don't use this AI variable, we
can substitute it with the underscore.
And basically this tells our compiler, Hey, we don't care about this value.
So just put a placeholder in there and we're not going to reference that value at all.
But in our next for Loop, we do know that we're going to reference J and and J is going to go from
zero to array length minus two.
And then here is where we are going to do our check.
So we're going to say if array of J is greater than array of J plus one, well, now we want to do our
swap.
So we will say erase swap and we have J and J plus one.
And at the very end we want to return our array and then we will get an error mismatch down here because
it says it expected a stroke of Vec i8 and we found immutable reference.
So we can quickly rectify that by saying two VEC and now our error is gone.
So now if we come back down here and we execute our code, we would expect to see the first vector of
5413 to print out a sorted vector which we see down here.
We see that we have one, two, three, four and five.
So our bubble sort is working correctly.
But to verify, let's run it on our second test case of our VEC two and let's do the same thing where
we just go ahead and print that out.
And if we run this again, we see we have one, two, four, five, eight, print it out, which is
sorted of the vector containing 51428.
So awesome.
So it looks like our bubble sort algorithm is indeed working correctly.
But if you remember from the previous lecture, there are times where our algorithm can be sorted or
excuse me, our vector can be sorted, but we're still executing these codes of these blocks of code.
Therefore we're wasting resources and time because we could still be executing at this loop, even though
we know that we're sorted in here.
So we can actually do a very slight little optimization here and we can create a immutable boolean called
Sorted and we'll go ahead and set it to true.
But we'll also at each new iteration of the loop, we'll make sure that it is set to true because we
know that if this block of code gets executed, then we are not sorted.
So that means we want it to keep sorting out.
But if this block of code never gets executed, then that means we are sorted.
And since we have this boolean here and it won't get updated in here because of it's sorted, this block
of code never gets updated.
Then we can put an if statement down here that says, Hey, if we're sorted then I want you to break
out of this loop, meaning this outer loop.
And so if sorted here, this basically says if sordid is true, then break out.
So with that little bit of optimization, just to make sure our code still functions as desired.
One, two, three, four, five and one, two, four, five and eight.
Those are the correct outputs.
So this is an optimization that would be better for a much larger array that does sort itself, let's
say, halfway through or we just cut the O of in squared in half.
So obviously with certain sizes of arrays, this would be a considerable performance increase.
But that was just something I wanted to point out, just to kind of keep in the back of your mind as
we go through these algorithms, I want you to try to think of ways that maybe you can optimize them.
And if you do have unique solutions to optimize some of these arrays because there's definitely optimizations
to be made, please share them with all with me and the rest of the students in the course.
But hopefully you enjoyed learning about bubble sort.
And we will continue looking at a few more algorithms in the next lecture.