OK, so now it is time for us to start going over some different types of sorting algorithms, and what
I'm going to do is just kind of start out with the most rudimentary basic sorting algorithms and work
our way up in terms of complexity and will not be going over every sorting algorithm because there's
a ton of sorting algorithms.
And I feel like there could be an entire course just on sorting.
But I don't have time for that.
So I'm just going to kind of pick a few basic ones, not go into a ton of detail on the efficiency because
that's going to be close.
That's going to be a big part of the second portion of the course.
So, you know, algorithms and analysis of algorithms.
So.
I'm just going to introduce you to a few thoughts, haven't figured out what other one's going to I'm
going to do, but the first of I want to start off with, which is pretty much considered to be the
most simple type of sort, is bubble sort.
So let's get into it.
We're going to go ahead and solve the problem that I gave you the challenge in the last lecture by using
bubble sort.
But first, I'd like to show you what bubble it is and how it works.
So the idea is that we have some array or vector right?
And all we're going to do for bubble sort is start at the left and go to the right and keep swapping
elements from left to right with the idea of bubbling up the larger values towards the right.
So basically, it's just, you know, five is bigger than this.
So let's swap them in kind of bubble five towards the right.
Five is still greater than this, so we bubble five further.
Five is still better than this, so we bubble five further.
So that's what we're going to be doing.
Keep swapping elements from left to right, over and over and over and tell the array is sorted.
So let's check out the first one is five greater than three.
Yes, it is.
So we're going to swap it, so we swap it.
Next is five greater than one.
Yes, it is.
So we're going to swap it.
Let's swap.
It is five greater than four.
Yes, it is.
So let's go ahead and swap it.
We now reach the end.
So let's go back to the beginning and do it all over again is three great and one.
Yes, it is.
We're going to swap them.
Is three greater than four.
No, it's not.
Is four and five.
No, it's not.
Now we go back to the beginning.
Oh, look.
One three four five.
They're all sorted now, so all numbers are now sorted.
We should be done right.
But what we're going to do is actually make something even more rudimentary.
We're not going to even add some code that makes this slightly more efficient and even knows that it's
done.
We're just going to write code that checks for all possible swaps for all elements in the array vector.
So you know, there's one two three four elements and we're going to try and just go through, you know,
like this, swap this swap in this swap.
So three different potential swaps for those four elements.
So it's not going to be very efficient, but that's what we're going to start out with.
So because we're just trying to make the most basic possible sorting algorithm.
So what I'm going to do is head over here.
I'm actually in the terminal and I'm going to go ahead and make a new file, and I'm going to call this
bubble story CP.
I'm going to include Io stream.
I will also include Vector.
I'm going to go ahead and use this and think you guys should get some practice with vectors, either
they're using their faces to do a main function.
Now put this or zero here.
I'm going to need to make a vector.
I'm going to make a vector integers and I call it my effect.
I'm going to need to make some sort of input variable.
I think I'm just going to call this and my aunt or something like that.
Now I'm going to go ahead and read in.
So I'll actually just say we're going to do five, right?
So I'll say four and I equals zero.
I have less than five have plus plus and I will just print out into and number right.
And that's when it said, I think and then I will sign in into my aunt.
And then what we will do is doing my vector push back so we can add it to our vector and it's going
to push back my aunt, right?
All right.
So that's a loop that should get input five times into an integer variable and then push that variable
back to the vector.
So now we need to think about sorting it right.
We filled our vector with numbers, and we need to now do both sort.
So what was bubble sort?
Well, we said we were going to go over all the possible swaps for all of the integers inside this race.
So there's five integers.
But what I'm going to do is is, say four and I was zero.
I less than and I will say my vec dot size because I'm just going to go through the whole size and I
will say I was plus.
And then in here, I'm going to need to now go over all the possible swaps that I could do for each
one of those.
So we're just going to try and attempt to bubble up.
Every single number in there, all the way to the end, so if it could potentially bubble up until the
end, which it doesn't really make sense, right?
Because if we're pushing like all these sort of things to the end?
There that everything that's been bubbling up and bumping into the end and kind of stacking up from
the right to the left, that's going to be all sorts of stuff, that whole thing that's stacked up from
right to left because we're bubbling stuff from left to right right.
And it's kind of like smashing up like traffic, backing up from the right to the left.
So we don't really need to go back through that sort of section, but we're just going to say whatever
will make the most brute force kind of algorithm that we can.
And I'll just say, for instance, J equals zero and I'll say J is less than my vector size.
And what I'm going to do here is do a minus one.
And why am I going to do that?
Well, think about the last element.
So I'm going to go ahead and here I'll just minimize this and we'll go back here, think about this
last element.
So if we're on the last.
So my vector net size is one two, three four, and this is zero one two three, so four would be out
here, right?
My vector size minus one is here, so last element and we're saying less than my vector size and minus
one, so we're talking about everything up to here.
Why would we want to stop here?
Well, what I'm going to be doing for my swabs is looking at where I am, which could be maximum here.
So if I'm here, this is the last spot since it's my exercise minus one, it's less than that.
So I'm going to try and look at I, which could be here and I +1 if I was to go all the way up to here,
if I looked at I +1, I'd be out here in no man's land.
So I don't want that.
So I want to stop here so I can still look at my plus one and potentially do a swap between these two.
I'm always going to look one ahead of where I am, so if I'm here, I'm going to look at here.
If I'm here, I'm going to look at here.
If I'm here, I'm going to look you here.
But I don't want to be here because if I am here, I don't want to have to look out into empty space.
So that's what I'm talking about.
So that's why I'm going to do less than my vector size minus one.
This is less than my vector size, so it'll go as long as it's not my vector size, it'll go up to the
last element.
This will go up to one before the last element.
I just want to make that clear.
So what do we do now?
Well, I want to put a check here, right?
We need to see if the thing we're at is greater than the thing to the rest of us.
So I'm going to say if my vector and I'm I say my vector j, because this is the loop that swaps.
This first loop is just saying, do all of this swapping and bubbling for as many times as there are
things in the vector which you notice this will go from zero to four.
Right?
So zero one to three four, that's five times this inner loop is the actual swapping bubbling part.
So that's why I'm using J.
I'm going to say if my Vector J is greater than my Vector J plus one, then what we want to do is we
want to swap them.
So this is where you might have been a little confused during the lecture, but I said something like
We don't really want to put my vector J equals my act j plus one and then just go here and then you're
like, Oh, great, now I'll just do it backwards.
My back j plus one equals my vector, j.
Oh, wait, no, I just said that my VC j is equal to my vector j plus one.
So now my vector J.
Holds my vote plus one, so when I go here and I say my big J plus one.
I'm just storing mine like J Plus one in my verdict, J Plus one, so they're just both going to have
the same thing.
I don't want that.
I just kind of overrode J.
It's been overwritten.
It's.
Copied over, and now I don't have it yet.
It's just been covered up, clobbered whatever you want to use, whatever term, so it doesn't even
exist anymore.
We lost that value there.
So what we have to do is actually save Jay in some sort of variable.
So why don't we make a new variable up here?
I'm going to say and temp.
So it's like a temporary variable, right?
And then what I'm going to say down here is I'm going to say temp equals my index, j.
So now what I can do is I've saved my leg j into temp and I haven't.
Oh, since I over wrote this, but I can just use a copy of it and now say my like j plus one equals
what used to be at my Beck J before it got overwritten with this.
So that's how you should do swaps.
You should make a temp variable.
You can also make your own swap function.
That would be a lot cleaner.
Just make a separate function.
And then all you have to do is replace all of this with a call to that swap function.
But I'm just going to do it in the for loop for now.
So I'm going to go ahead and add this little bracket here for that, and then I'm going to add one more
bracket there.
And now we need to do is go ahead and print this out.
So I'm just going to have pretty much another loop just like this.
I actually could probably just copy paste this, come down here or what's actually I want to do that,
you see,
so I can actually just come here, paste this and then I can, like, delete this because I only want
to see our stuff so I can see out and I will see out my next high ranking.
It's going to be five.
I really should put my vector size in here, though, because that's a lot cleaner.
The five is just how many we want to start out with.
And then subsequently, I can use my vector size.
This just kind of a cleaner way to go about it, so now I have these three loops, I'll go ahead and
print that out.
I should probably put a little space between them just so it looks kind of clean.
So let's go ahead and test this out.
It should be good to go.
I'm going to go ahead and pilot.
So now I can runs that out into some numbers.
So how about we do like five three?
One two.
And seven.
And there we see one, two, three, five, seven, it's in order we should probably put a new line,
though, so let me go back to bubble bubble sort C.P..
We'll go ahead and just see out in the line here.
I'll save this running in an analogy.
Just like take some random stuff.
And there we go.
Look, we got them all in order.
720 for thirty to forty five.
Sixty seven.
So pretty simple.
This is like the most simple sort that you could do if you weren't able to figure out the sort of thing,
don't worry, it is a little bit confusing the whole swapping thing and knowing how to set it up.
You might have come up with another sorting algorithm that already exists.
So it would be cool to go check to see if what you did is something that already exists.
I'm going to be going over some other algorithms and you may realize when we go over them that this
is the algorithm that you actually came up with.
There are some sorting algorithms out there that are much more efficient than Bulbasaur.
In fact, mobile is pretty much the worst sorting algorithm out of them all in terms of speed or efficiency.
But nevertheless, it gets the job done, and that's what's important.
In the beginning, we want to find a naive brute force solution just so we can at least solve the problem,
right?
Afterwards, we can look at making a better, more efficient solution.
This is something that will come up a lot in the algorithms section of the course.
Right now, we're not going to focus too heavy on trying to optimize all of our solutions, but we will
cover a few algorithms that can sort and come in like slightly more complex ways, maybe not necessarily
more efficient, but just look into some different algorithms.
First sorting.
So, all right.
So with that, I will see you in the next lecture.