Hi everyone.
In this video let's discuss the logic of the bubble sort.
Now let's say that we are given an array of integers seven, two, three, eight, one.
Now initially the pointer would be placed at the beginning element of the given array, and we identify
the element which is next to this.
All right.
So the indices over here 01234.
So the pointer is at index zero.
And the next element is at index one.
Now we are going to check or compare these two values.
And if needed we will swap them.
Now seven and two is not in the ascending order right.
Two is less than seven.
So we need to swap them.
So we will swap these two values.
All right.
So now at this point the pointer was at index zero.
Now we got the array to 27381.
Now again the indices are 01234.
Now the pointer was at zero.
Now we move the pointer to the next index which is one.
And the value next to that is three.
Now we are going to compare seven and three.
Now they are not in order right.
Three is less than seven.
So we will swap them right.
So we get 23781.
And again we move this pointer to the next index which is at two.
And we compare the value over here at at index two.
Now we have seven.
All right.
So this was the previous array.
Now we changed it again.
We are looking at the indices.
At this point the pointer was at index one.
At this point the pointer is at index two, and we are comparing the values at index two and index three,
seven and eight.
They are in order.
So we don't swap and we move the pointer.
And we are going to compare the values at the indices three and four which is eight and one.
And they are not in order.
Therefore we will swap them and we get two, three, seven, one and eight.
Now this is called one pass.
So we have done n operations right.
We have gone through the given array once.
Now notice that after one pass the largest element is now at the right most place which is eight.
So we don't need to shift this any longer.
This now again this part of the array is still not sorted.
Right.
But this element which is the largest element is now at its right place, which is the right most place.
Once we have sorted the array, it should be over here.
Right.
All right.
So we are now over here.
We have completed one pass.
Now what we do is again we have our pointer over here.
And we check that value with the next value.
Now we keep doing this.
But notice that we don't compare this value with the last position because as we already discussed,
this is fixed.
The position of value eight, which is the largest value, is already fixed.
So we don't compare these two.
So we stop at this point.
All right.
So these are the positions that we are going to compare zero with position one one with position two
two with position three.
Now after again remember we are not comparing the last element because as we said this is already fixed.
Eight is at the right position, which is the largest value and it is at the right most position.
Now we keep doing this, we keep having passes till in one pass.
If we don't do any swap, if you don't do any swap in a particular pass, that means it's already sorted,
right?
If it's not already sorted, we would have done at least one pass.
But if in one pass we don't do any swaps, it means that the array is sorted and we can stop now.
For example, in this pass we can see that we'll compare two and three.
So they are in order.
So we don't need to swap.
We will compare three and seven.
They are in order.
So we don't need to swap.
But seven and one they are not in order.
So we will swap right.
So we cannot stop at this point also.
So after doing this swap the array will look like this 23178.
We have swapped these two so we got one and seven over here.
Now this is the second pass.
Now notice that at the end of the second pass the second largest value is at its right position after
the end of the first pass, the largest value was that its right position.
Now after the second pass, we have the second largest value at the second place from the right.
Right.
Which is this place.
Now, in the next pass, we don't need to compare these two values.
They are fixed, they are in the right position.
So we just need to do two comparisons two and three and three and one.
Now when we do two and three they are already in order.
So we don't need to swap them.
But when we compare three and one they are not in order.
So we will swap them and we get two, one, three, seven and eight.
Now in the next pass we will compare only two and one because over here notice the third largest element,
which is three is now in the correct place.
So these three elements or integers are in the correct place.
So we don't need to compare them any further.
So in the next pass we will only compare these two.
And they need to be changed.
The order has to be changed.
So we change them.
We swap them and we get 12378 which is the correct order.
So the input array has been sorted.
So this is how Bubblesort works.
Now just to demonstrate in the case where we had the input array as 23718, we saw that we had to make
swaps up to the end.
Right now let's say that the input array is partially sorted.
Like let's say it's 12837.
So it's partially sorted.
Now in the first pass we'll compare one and two.
We don't need to swap.
We'll compare two and eight.
We don't need to swap.
We'll compare then eight and three.
In this case we need to swap right.
So when we swap them the array will become 12387.
And then we will compare eight and seven.
Right.
So when we compare eight and seven again we will swap.
And we get 12378.
And you can see that this is already sorted.
Right.
And this happened in one pass.
Now what happens is in the next pass we will not take, we will not compare this element because as
we've discussed after the first pass, this is already in the right place.
But we will do these comparisons right.
We'll compare the positions zero and one, the values at index zero and one, the values at index one
and two, the value at index two and three.
So we'll make these comparisons in the next pass.
And you can see that over here.
We don't need to make any swaps right over here.
We don't need any any swaps when we compare.
These two.
We don't need any swaps.
And when we compare these two, we don't need any swaps.
So there is no swap in this pass.
And that means that this array is already sorted and therefore we can stop.
So this is how the bubble sort works.
And let's take a quick look at the complexity analysis of the bubble sort.
Now over here you can see that the time complexity of the bubble sort is O of n square.
Right.
Why is that so in one pass.
In one pass we are doing n operations or almost N operations.
Right?
We are comparing two and three, three and seven etc..
Right.
So we are doing almost n operations in one pass.
Now if we have n elements we need to do almost n passes.
Right.
So that's why n into n the time complexity is O of n square.
Now what about.
And again remember this is when we implement this you can just think of it again.
It will become more clear when we look at the code.
This will be implemented as a nested for loop.
Right.
We we could write this as a nested for loop.
And when you have a nested for loop it's o of n square, right.
Because for each element again you're traversing the given array.
Right.
So we'll see that again more clearly when we look at the code.
You can also think of it in this manner.
Over here we have seen that after one pass the largest element is at the right place, right at the
right most place after one pass.
So if we have n elements, the worst case, we would need n passes to get all of them in their respective
right place.
So that's why for n elements we need n passes and in one pass we are doing n operations.
Therefore, the time complexity of this solution is O of n square.
Now what about the space complexity?
The space complexity is O of one because we are not using any additional memory, right?
We are just swapping in place.
We are not making a new array or something like that.
So the space complexity of this solution is O of one.
Now remember O of n square is not the best case scenario of bubble sort.
The best case scenario happens when you are already given when the input array itself is sorted.
For example.
In this case, if the input array itself was 1378, after one pass, we will identify that no swap had
to be made and we can stop right?
In that case, the time complexity would be O of N, but that's not the average or the worst case.
That's the best case, right?
So we cannot say that that's the time complexity.
The time complexity of the bubble sort is O of n square.