Hello all and welcome back.
So in this video let us now move forward.
And now let's try to code the Bubblesort algorithm based on our discussion.
Now for many of you, this might be the very first algorithm which you are coding for sorting.
So I want to explain you one thing right.
Please make sure that you are understanding the way I am trying to go to the problem, rather than just
chasing behind the solution.
Okay, in this whole course, my aim is to make sure that you are comfortable with understanding that
how we have to reach to a particular problem and not just basically make sure that we remember the solution,
or we have to remember this particular code.
I have seen many students, they try to remember the code and that is like the worst thing you can do,
believe me, because it is not going to be helpful in a long run.
If you are planning for tier one companies like Google, Amazon, Microsoft.
Interviewer is more interested in your approach then uh, like seeing you how quickly you can code anything.
Okay, great.
So let us take an example, the same example everyone.
So we had this thing 1225 1134 90 and 22 right now in the last class, we actually did a dry run on
this of the first pass.
So let me just go above and see.
This is how we have done the overall dry run.
Right.
So here you will notice that we are just comparing the adjacent elements.
And we are running five passes okay.
That means if the length of my array is six then I need five passes.
Right now we will just think about a single pass okay?
And not all the passes.
I know that a single pass doesn't sort my entire array, it just sorts the it just take the largest
element to the right position.
But that is how you break the problem.
Okay, great.
So from this particular thing we have these two things here.
So let us now try to code and just we will try to code what we are visualizing or understanding okay.
So instead of just directly starting with code we have to first see how the problem is getting broken
in our understanding.
Great.
So let us take a function bubble sort.
In this function I will be getting an array okay I have to make the changes in this particular area
or list only and I have to just return that.
So unsorted list equals 1225, 11, 34, 90 and 22.
Once this unsorted list I have, I will be getting a sorted list.
Okay.
And as I said, we can use in Python arrays and list interchangeably.
That is all fine.
You now are aware that list are the way we use arrays in Python.
Normally these are all the algorithms which are run on an array.
Okay, so don't get confused in that.
If you have not seen the previous video where I explained that, please make sure that you see that
once.
I will be just calling the Bubblesort algorithm with my unsorted list and I can just say no sorted elements.
Sorted list.
So I am finally going to get my sorted list.
That thing is for sure.
Now let us see.
Let me just zoom in a little bit more.
Yeah.
First thing is that I can get the N, which is the length of my list or array.
Great.
This is something which you have to get first.
Now, I know for the first pass I have to do n minus one work.
Right.
So let us see that in coding everyone for.
Let me write it J maybe.
Okay so for j in range zero to N minus one.
This is what I have to do.
Let me just zoom it out because that will keep popping up.
Zero to N minus one.
Now let us understand what exactly we have to compare.
So pay attention here everyone.
This time let us talk in terms of indexes okay.
So this is zero, 1234 and five.
When I start my j is equal to zero okay.
So j is zero when I start.
And I compare it with the j plus one element which is the first element.
Great.
Then my j will become one and this time I will compare one and two.
So what I believe we can use here is j plus one.
Okay great.
So it will become one.
It will become two.
Similarly I move to two then three.
When I move to three.
One minute.
Yeah.
So when I move to three, then it's four.
And when I'm four.
This is five.
So this is the comparison when I'm on four and five.
Now let's say it is five and six.
But I think there is a problem if we write or take j till n.
So in this case my n will be equal to five right.
We are starting from zero.
So the last index is five.
So you can take it as last index n minus one.
Normally when you write when you write this thing okay.
So always remember this as well.
Very important.
Whenever you write let me write it in a different way.
So you remember range zero to length okay.
You get elements from zero to length minus one.
You must have done those coding exercises which I have given you in the inbuilt data structure, just
to have your basics revised after you must have studied for all the Python basics from Christopher videos.
So it is again very important that you have these things clear.
That was the major motive behind those coding exercises.
So in a similar way, if I am running from 0 to 0 to length, okay, I will be getting till this thing
from 0 to 5 because length is six.
But I see one thing, this last one, I don't need, this last one I don't need because I don't have
six.
Right everyone, this is something which we saw above as well.
We needed in the first pass.
We needed just five steps, right?
So what does that mean?
Everyone let us now just try to code this out.
Yeah.
For J in range zero N minus one.
This is why we are taking n minus one here.
These boundaries are very important okay.
Now what are we comparing.
If array of j is greater than array of j plus one.
All I'm saying is, if this element, let's say in this case 25, is greater than the element next to
it.
J plus one, then I will be swapping them.
Okay.
So a very good way we can swap in Python is something like this.
So array of j and array of j plus one equals.
Now I can just write them in an opposite order.
So I can copy this here.
And I can copy this here.
So what effectively this does pay attention.
It actually says that j will become j plus one array of j.
And this will become this.
So it swap them internally okay.
And that's a very good way you can swap uh with a temporary variable as well.
I think that you must have done in any of the coding exercise.
But this is a smart way of doing overall swapping in Python.
Great.
So once you have done this, once you have now written all this full step, you can be sure that one
element okay, the largest element will be at the last.
And we can check that as well.
Return array.
So let us run this.
We know that it will not be sorted.
But let's see what is the intermediate output.
And I see the 90 getting to the last.
Let us make it 120 and try to run to see if actually 120 is going to the last or not.
And if I run this again you see 120 going to the last.
So what we saw in our visualization, in our understanding step by step, we have just noted it down
in our code.
That is how coding should be.
Okay great.
Now since our array is not sorted, what we have to do, we have to again do the second pass.
So this time I will be starting off again.
So this whole step where I start with J zero.
Let me draw it here.
So one second everyone.
Yeah.
So this was my pass one.
Everyone.
This was the pass one.
Now I will do the same thing for pass two.
As we saw.
Right.
So we saw the same in the overall visualization on Hackerearth as well.
This time I will have J.
I will have J plus one.
Everything will be same.
I will start from zero okay.
And I will compare them.
Maybe we can write what we are getting after the first pass.
So it is 1211, 25, 34, 22 and 90.
This time again I will start and just keep on doing the comparison.
Okay.
This is something which we saw in the last overall example, last in the video in Hackerearth and as
well as in our own Dryrun, we know that we have to do this thing n minus one times.
Again, the reason we have to do this n minus one time is to make sure that n minus one elements are
at the right position.
Okay, for that, I will just show you one more thing as well.
So pay attention everyone.
If, let's say for passes in range two, let's say I just do it for two times.
And now let us see what our output will be.
We saw that in first pass we were able to get the largest element to the end.
That means in the second pass, I will get two large elements in the right position and see 90 and 120
is working fine.
So I hope you are able to understand this everyone.
If I run this n minus one times now okay, that would mean that my n minus one largest element will
go to the right position and I can show you that as well.
N is six.
So let us see this one by 13C1 second.
And then I have to rerun it.
So it takes a second to save that.
That's why the output was same 34.
Now we see this thing.
If I do it for then I'm getting it like this.
Now let me run it again.
Yeah, I'm getting it like this.
It is sorted in this case, but that should not be a problem if I do five finally it will be sorted.
Okay, so all I am saying is I have to do this thing n minus one times.
Now in the same way n zero to n like you, I hope you know that this is zero by default.
So this will be running n minus one times.
And now actually you will be getting your array sorted after you run it.
So breaking the problem very smartly into smaller steps.
Now you are able to get this.
But programming is not just about getting the answer.
It is to see.
Can you try to optimize anything more?
Okay, let us see what we learned in our last example.
So last video when I am writing this zero one then Two three.
Three, four.
And finally I will write this.
Four and five.
Now, if you remember, we do we need to do this can do this.
Overall comparison in the last we saw the same in the hackerearth as well that this used to turn green
right.
So if you go to the very starting and I move the element to the 90 to its right position, it used to
turn green.
And now let us see for the second pass, are we doing this comparison.
The understanding is if something has reached to its right position, why do we need to compare it with
anything now.
So you will see that the last comparison actually will not happen, 34 will not get compared to 90.
Okay, so pay attention everyone.
See, 34 is here, 90 is here.
This time we will not be comparing 34 to 90, because I know 3490 has reached the right position in
the last pass, because that is what my pass does, right?
Each pass that is what is happening.
So for that, what I have to do, first one, I have to run for all n minus one element so I can write
it as well.
Everyone so that you remember pay attention.
Again this is very important.
First pass.
Implies n minus one.
Second pass I can say that I just have to compare for n minus two right.
So just n minus two element in a similar way.
Third pass I have to do for n minus three.
Now I just need something to subtract from here from here.
Okay.
So that this thing happens what can be that thing.
I think this passes is a very good overall number for that.
This pass will start from zero.
So if I do minus passes okay it will be n minus one -0 initially.
Then it will be n minus one minus one, which specifically mean in the second pass I will get n minus
two.
In the third pass it will be n minus one minus two, which will be n minus three.
This time we are starting from zero okay.
So my passes are starting from zero.
That's why in the second pass I am taking n minus three and in this way I will be able to optimize it
a lot.
Right?
So let us run this now to see if we are getting it.
The overall output.
Nice.
Great.
Now if you remember in the last overall video I asked you to all in the problem solving video, I asked
you to check for multiple things.
Right?
Let's say you are giving an empty array.
I am getting the answer right.
If you are given an array like this, will it work on this?
This is a very good case where it is completely sorted in an opposite manner.
If I run this now, I am able to see that it is running fine.
Okay, so that's how you always check your solution.
It should not just be check on the given test cases.
Try to think of more test cases, the boundary and the edge cases as they are the reason why your code
can fail.
Okay, so great everyone.
I hope you are able to understand each and every step that how we are going to write the code for any
algorithm moving forward.
Again, it is very important to understand and break down your breakdown your knowledge and then try
to code it.
So we first wrote this for a single pass what we are doing.
And then we used this passes to see how many pass we have to do.
Okay.
That's the way we will be coding in this whole course.
So please make sure that when you try it out in the coding exercise, you are doing justice and giving
enough time.
That is a lot required.
Okay, great everyone.
So I hope this is clear.
Now if you have done this already in the coding exercise, pretty good.
If not, just try to now code it again based on this understanding, and I'm pretty sure you will be
able to code the same from scratch.