So we have successfully coded the bubble sort.
Now let's take a sample input.
Let's say it's one, two four, five, three and walk through the code and see what's happening over
here.
Now we call the bubble sort function.
And we pass this array.
Now initially sorted is set to false.
All right.
And the counter is equal to zero.
All right.
Now sorted is false.
So we come into the while loop and immediately we set sorted to true.
All right now I is equal to zero.
Okay.
So I is equal to zero.
And this will keep repeating till I is no longer less than array dot length minus one minus counter.
So over here the length is five.
So five minus one is four.
So it will keep repeating till three right.
It should be less than four.
So it will repeat for zero.
It will work for one two and three right.
Again remember.
Why is that so.
Because we need to compare a value with the next value.
So if we keep if if we had an equal to over here, we would go till I till the last element.
But then over here you can see that we have array I plus one.
So there would nothing be there as the next element.
That's why we have only less than over here.
So this will keep repeating for I012 and three.
All right.
Now initially I is equal to zero.
Now I plus one is equal to one.
So we are comparing these two elements right.
The elements at the zeroth and the one index.
So let me write the indices in a small manner over here 0123 and four.
We are comparing the indices at zero and one.
And we see that they are not uh.
So over here we see that they are already in order.
So we don't call the swap function.
Now after this I is equal to one, right?
I is equal to one.
And we are comparing these two.
Now these two are also in order.
So we don't call the swap function.
After this I becomes two.
Right when I is equal to two we are comparing two and three.
The values at the indices two and three.
They are also in order.
So we don't call the swap function again we increment I.
So as we have discussed over here it goes till three.
So when I is equal to three we are comparing these two right.
The values at index three and four.
Now these are not in order.
So we call the swap function and we swap five and three right.
So when we swap five and three the array becomes 1243 and five.
So these two values are swapped.
And when we enter over here we set sorted is equal to false.
So when we started we had made sorted true.
But in this pass this is one pass right.
So in this pass we had to make a swap.
Therefore sorted became false.
And we come out of the for loop we increment counter.
So counter was zero over here.
So counter becomes one right.
And we check whether sorted is false.
So sorted is false because it became false over here.
So again we enter the while loop and sorted is set to true.
Right.
And then for I from zero up to array dot length minus one minus counter.
So in this case counter is one.
So array dot length is five five minus one is four minus one is three.
So it has to be less than three right.
So it will work for zero one and two.
So these are the three iterations that will happen over here right.
Remember we don't need to compare the last element.
It's already in the correct position.
We have discussed that right.
So that's why we just need these three uh comparisons in this particular pass.
So when I is equal to zero we are going to compare these two values.
And they are already in order.
When I is equal to one we are going to compare these two values.
They're also in order.
And when I is equal to two we are going to compare these two.
And these two are not in order right.
So again we will enter over here.
We will call the swap function.
And we will swap these two values right.
So we get 12345.
And sorted is set to false.
Right.
And we come out of this right now when we are coming out of this and it was at I is equal to two.
Right.
So this is over.
That's why we come out and we increment the counter.
Now counter is set to two.
Right counter becomes two.
Let me write that over here.
Counter becomes two.
And again sorted is false right.
We made it false over here.
So it enters the while loop.
And we check over here.
While I is less than array dot length which is five five minus one is four minus two which is two.
So it has to be less than two.
So it will work only for zero and one.
But that's fine.
So this at point zero will compare these two right.
And at point one we'll compare these two.
Right.
So they are already in order.
And these two are already in their fixed position.
So we don't need to compare them.
So at this point you can see that we did not make any swap.
Therefore sorted stays true.
We made sorted true over here and sorted stays true.
You can see that all these five elements are sorted right.
So that's why we can stop at this point.
Sorted is set to true.
And we can return the array and we have the array in sorted manner.
Now this is how we solved, uh this is how the bubble sort works.
Now what's the time complexity of this.
We have seen that the time complexity of this is o of n square.
Why is that so over here you can see that we are making n passes.
Right.
So, uh, how how do we how do we say that.
And passes is the worst case scenario.
If all the elements had to be shifted right?
If swaps kept on happening.
Now, when we look at the time complexity, we always look at the worst case scenario.
Right now the process is taken care by the while loop, right?
So we keep doing the while loop till we need to make more passes.
And in each pass you can see that over here in the for loop we are doing N operations.
So over here we have the while loop which which is contributing N operations.
And in each of these N operations we are having the for loop.
Right.
So this is nested inside the while loop.
And for each one of these we are doing n operations.
So that's why the time complexity is n into n which is n square.
So the time complexity is O of n square right now.
So n passes.
And in each pass we're doing n operations.
In one pass we have n operations.
So that's why n into n n square is the time complexity.
And the space complexity is O of one.
Why is that so.
Because we are not using any additional space.
We are not making a new array.
So it's running in constant space or O of one.