Hello all and welcome back.
So in this video let us now continue our discussion on searching and sorting algorithm.
And now let's start with sorting.
Now sorting is a process through which we are able to arrange any number of elements in an increasing
or decreasing order.
Now there are lots of applications of sorting.
That's why the range of algorithm through which we can do sorting becomes a lot important in our overall
algorithmic study.
You can think of in real world as well when you sort on Amazon or Flipkart by price, or let's say by
date.
These are all the different, different operations which we have to do from a user endpoint, as well
as if we think about from a database endpoint.
For the companies, sorting is actually something which is used a lot to maybe just fetch the latest
records from even millions or billions of records right now.
That was the basic idea behind sorting.
Now there are many different algorithms which we are going to study as we equip ourselves with more
advanced concepts in DSA.
Okay, now to start with, we are going to learn the bubble sort algorithm.
Okay, so let's start everyone, let me give you the basic idea behind bubble sort.
So let's say we are given some elements.
The elements are like this 1225
1134 90 and 22.
So the way I remember bubble sort is that you have to create a bubble around two elements.
Now you can of course, in a minimum compare two elements.
Right.
Because if you want to do sorting, that basically means that you are given some elements.
You have to correct their order, or you have to make sure that the smallest one gets to the starting
and the largest to the end.
Assuming that we are doing the sorting in ascending order, right.
So the way I remember it, that you create a bubble around two elements, and if the order is not correct,
you swap them.
Okay.
So let's say in the very first, let's now just go through our array and try to create bubble one by
one.
Okay.
Great.
So let's say this is the first two I'm comparing everyone.
So first step here I think the order is fine.
So we don't need to do anything right now.
Let us move to the second step.
In the second step I will be comparing 25 and 11 because they are not in right order.
25 is greater than 11.
I will be swapping them.
Hence the order will become something like this 25, 34, 90 and 22 and we can write 12 in the starting
now.
Let us see the third one everyone.
So third swap or third pass.
In third pass we are now going to compare 25 and 34.
Right now they seem to be in the right order, which basically means I don't have to do anything.
If I take the fourth pass, then I will be comparing 34 and 90.
Okay, in this 34 and 90, again, this seems to be in the right order, so I don't need to do anything.
The fifth pass okay will be in which I compare 90 and 22.
So let me write these down as well.
3490 it is right.
This was wrong.
And I have 25 and it was not 25 and 11.
So instead we had 11 and 25 right.
So we had 11 and 25.
So we didn't do anything right.
Great.
So let us now move forward everyone.
This was actually 25 and 11 so that we have to solve them.
Great.
Now what will happen in 90 and 1922.
The order is again wrong, so I have to make sure that I swap them.
And in the end, after one complete pass, we will get our array or the list.
Something like this.
Great.
So this is the overall situation of my array after I did the one pass.
Is it sorted?
As of now I don't guess it's sorted right?
We can still see that 12 is earlier than 11.
It should not be.
So what have I achieved after this one pass?
Well, there are two.
Very good observation.
The first thing is that.
The largest element.
That is 90 in our example is at the right position.
And the second thing is that we needed.
Length minus one.
Right.
Length of our array minus one passes to do that.
So thing is to understand the process right in this process, after doing this thing I am able to check
that two things are right 90 the greatest element is at the last.
And if you think about this, it is going to happen.
If the 90 would have been in the starting, let's say this would have been 90, then I will have to
keep swapping every pair of elements till I am able to reach till the end.
So after one pass in bubble sort, we are able to get the largest element in the end.
Okay.
And the second thing is that there were six elements and I needed five overall passes in the first.
For the first overall element, right.
First largest element.
The reason is that of course we are doing comparison.
So for six elements adjacent comparison are six.
So I can compare them one, then 234 and five.
Right everyone.
So that's the basic idea behind Bubblesort.
Now I will continue my process and let us do it for one more pass.
Let us just do the second process now.
This time I will again start to compare.
So this I will say first okay, after done.
So this is the second pass and first step.
Let me write second pass here.
Second pass okay great.
Now we are going to compare them.
They are not in the right position.
So we have to swap 1112 2534 22 and 90.
Great.
So now I have to do the second in which I will compare these two.
This seems to be right.
In third I will compare these two.
Seems to be right in fourth I will compare these two, which is 34 and 22, which seems to be wrong.
Hence I need to swap these two elements.
So 12, 2522 and 3490.
Now I can do the last step as well.
I can do the fifth comparison, but if we pay focus it is actually not required because I know in the
first pass, the last element which I get after the first pass is the greatest element.
So we know that we have 90 here, which is the overall greatest element.
But now the next observation in this is in second pass.
The second largest element.
Is at the right position.
Right position.
Right everyone.
So what does this mean effectively is that if you do n minus one passes and in each and every pass,
if you are able to compare your elements one by one, you will be able to finally sort your array,
because after each pass, you are able to put one element at its correct position.
After n minus one passes, n minus one elements will be at correct position, and the leftover last
position will be for the last element, which of course will be true.
Okay, so let us try to visualize this a little bit more better everyone.
So let us go to our website which I have found to help you visualize.
So this is the same array which we took 1225 1134 and 90.
So let us try to visualize this on a hackerearth.
So this is the initial state right now.
Pay attention.
I will be initially comparing these two okay.
So for each pass we will move left to right swapping adjacent element as needed.
Each pass moves the next larger element into its final position okay, which will be shown in green.
So let us move forward now everyone See it's starting the past zero in this pass.
It will go and compare two two elements first.
These two are getting compared as the order is right.
Nothing is going to happen.
Great.
Now the next two.
This time as we saw in the overall working when we did the dry run, 11 and 25 are in the wrong order.
11 should be earlier than 25.
This means now they are swapped.
Now they are in the right order.
Should be fine.
Next 34 and 90 okay.
Seems to be right.
And final 22 and 90.
So we will be swapping them.
And now you will see this element has reached its correct position.
Let us now do the second pass.
So it is starting pass one or like zero indexing.
So no worries.
Now again we will be doing the same thing.
These two swap them.
Next two are right.
Next two are also right.
And they can be wrong as well.
You just have to make sure that you swap them if they are wrong.
And finally 34 and 22 which are wrong.
So let us swap them.
Right everyone, now you will see that 34 has reached the right position.
34 has reached the right position.
It is actually not required to compare 34 and 90, because we know in the first pass the largest element
will be at the right position.
Now, if I do the one more thing, let's say 11 and 12, they are in the right position.
12 and 25 seems to be in the right position, 25 and 22 seems to be in the right position.
So we have just swapped them and now 25 is in the right position.
Now we will have to repeat the process.
Like we can see that okay it is sorted.
But that doesn't mean we should stop because it can happen that something bigger is kept here.
Okay.
So we have to continue the process now.
Let us move forward.
Now we are starting the past three.
In past three we will see.
The first two are right.
Next two are right.
So now this one has reached here.
Similarly last pass which is four because we started from zero.
Each element again we will check.
And finally you will see that our array is completely sorted.
N minus one are at the right position.
The last one by default means that it will be at the right position because it has just one position
left, and if all other are at the right position, then that implies that the last one will also be
for sure at the position it should be.
Okay, so that's the basic idea behind bubble sort.
Please make sure that you remember the visualization and the way we do it.
Uh, like basically making a bubble because as we learn more and more sorting algorithm, you will get
confused between them.
That is like something which used to happen with me.
And that's why I have made these mnemonics to remember these things that we will be creating bubble
around two, uh, elements and then see if we have to swap them or not.
Now everyone, based on this understanding what I want all of you to do is to try out the code.
Okay?
I can give you a basic hint.
And in the next video we will write a workable code.
Based on our discussion, we will be using two loops.
First loop will be the pass.
Okay, how many passes we have done.
So we have seen that we have to do the passes till n minus one, right?
Second loop will make sure that each and every element gets compared to its adjacent element.
If the order is fine, we can move forward.
If it is wrong, then we have to make sure that we don't move forward and swap them first.
One more thing to remember is that after each and every swap, we have to make sure that somehow we
reduce that, hey, this element has gone to his right position.
Please don't just compare it with the the like the don't do the comparison here.
Okay, so that's the basic idea.
Now let's meet in the next video where based on our understanding, based on all the visualization which
we have seen and understood, we will try to write the code for this.
Okay.