L-3.6: How Bubble Sort Works | Performance of Bubble Sort | All Imp Points with Example | Algorithm

Hello friends, welcome to Gate Smashers. In this video we are going to discuss about bubble sort. And in this video we are going to discuss all the important points related to bubble sort.

Which are your competitive exams, college or university level exams. Even it will be very beneficial for your placements. So guys, like the video quickly.

Subscribe the channel if you haven't done it yet. And please press the bell button so that you get all the latest notifications. Let's start first of all.

Let's see how bubble sort works. Means how the algorithm of bubble sort works. We have an unsorted array.

Now what we have to do with it? We have to sort it using the bubble sort. So what we do?

We start with the first element. Means what I gave it as? I made it a bubble element.

Now we compare it with the next element. We have to compare this first element with the next element. If the next element is small.

Means if the next element is smaller than this bubble. Then what you have to do here? Swap.

If the next element is big. Then you have to do nothing. Your bubble will shift to the next element.

Means let's say 10 greater than 9. This element is smaller than the bubble. So what you have to do here?

Swap it. 10 came here. Rest of the elements are as it is.

You have to do nothing else. Now who is your bubble still? 10.

See the next element 11. You have to compare it only with the next. So 10 is compared with 11.

So what is 11? Bigger. 11 is bigger means you have to shift the bubble.

Now who is the bubble? 11 is the bubble element. Now you have to compare 11 with 6.

So the next element is smaller than the bubble. So swap it. 9, 10, 6, 11, 15, 2.

See the next element is bigger than the bubble. Means now you have to shift the bubble. Otherwise we swap it.

Otherwise we have to shift the bubble only. Means 9, 10, 6, 11, 15 will be the bubble element and next is 2. So when are we swapping?

We are swapping in one case only. If the next element is smaller than the bubble. So see the next element is smaller then here 9, 10, 6, 11, 2, 15.

So your first pass is completed here. What is completed here? It is pass 1 or you can call it step 1.

So always remember in bubble sort that after every pass the maximum element will be at the correct position. Means what will happen after the first pass? The biggest element from the whole array will reach its exact position.

So see 15 has reached its exact position. Now you don't have to consider 15. Means now we are at N-1.

If total length is N then we will consider N-1 only for the next pass. So what did we take in the next pass? Let's say we took 9 as bubble.

So if I took 9 as bubble then you don't have to touch 15. So what is the next element? It is bigger so Make 10 as bubble.

Next 6 is smaller than the bubble. Swap it. In swap 6 will come here, 10 will come here.

Next 15 as it is, keep writing. Then 11, 11 is bigger than 10. So what you have to do now?

Who will be the bubble? 11 will be the bubble. No need of swapping.

Next element 2 which is less than the bubble. Now what you have to do? Swap it here.

So 2 will come here, 11 will come here. And rest of the elements are same as it is. So see now we have completed the second pass.

Completing the second pass means that your second largest element has reached its correct position. So see both the elements have reached their correct position. Now you have to run the third pass.

So in the third pass remember N-2. Earlier we considered N-1. Now we will consider N-2.

Means in next who will be? 9 will be the bubble element. Then you compare it with the 6.

So then it will be 6, 9 will come here. Then 10, 2 will come here. Then 6, 9 will be the bubble element.

10 will be 2. And in the last what will happen? 6, 10 will go here.

2 will come here. So 10 will come here. Means 11 and 15 as it is.

So see after the third pass all three elements are sorted. So here you have to move one by one in this way. So which questions are possible here?

First question is possible. After 2 pass, after 3 pass how the array will look like? We can ask you this question.

Second, number of swappings required. If you are given a question, we can ask you to sort it. Count the total number of swappings.

Third important point is its time complexity. So see we quickly take out the time complexity in worst case. What is the meaning of worst case?

Let's say if I take the array unsorted, 9, 6, 7, 5, 4. If I take it in this way, means in decreasing order. So we saw what bubble sort does.

After every pass the maximum element will be at the right most position. Will reach here. So see if I take the array in decreasing order.

Then obviously we have to take 9 till here. We have to take it to the last position. So obviously this is the worst case.

Because in this number of swappings will be maximum. First you will do 9 with 6, then it will be 6, 9. Then with this, then with this, then with this.

Then 9 will reach its right position. So if we talk, let's say there are n number of elements in decreasing order. So obviously how many times I am comparing the first element.

How many times my swapping will be. Obviously n-1 times my swapping. See what we did here, we compared 9 with all.

So when we compared 9 here, we are doing it one by one. So 15 will reach here. Now to reach the maximum element here, in the worst case it can have 1, 2, 3, 4.

See how many swaps happened. I had to do 4 swaps. What were the number of elements?

1, 2, 3, 4, 5. So took 5 elements, had to do 4 swaps. If there are n elements, then how many swaps will be maximum?

n-1. Next time, see 9 will reach its position. Next time what will you do?

You will compare 6. So with which will you compare 6? With 7, with 5, with 4.

Means next time what will be the number of comparison? n-2. Reason?

9 has reached its correct position. So don't consider that. And the second first element which you want to reach, obviously it will not count.

So n-2. Next time n-3. Up to where will this value go?

Up to 1. So if you solve this, then what will come? nxn-1/2, which is n2-n/2, which can be written as order of n square.

Reason, n square is the quadratic time complexity. This is linear, so which is the larger of both? n square.

So order of n square will come here. And how is this coming? Let's say I take this series.

1, 2, 3, 4 up to n minus 2, n minus 1. If I write this series like this. n minus 1, n minus 2, n minus 3, n minus 4 up to 2, 1.

Can we write this? First I wrote the series straight, then I wrote it upside down. Now if I combine these two, then what will be?

2s. Total both. What will be 2s?

n. What will be this? Here n minus 1 plus 1, that is n, n minus 2 plus 2, that will be n, n, n up to what?

n, n. Means how many times n will come? Your n minus 1 times n will come.

So what will be the value of s? 2 will come down. This is how we generally solve it.

So this is a formula, mathematical calculation. n into n minus 1 divided by 2. So what will be your total?

Order of n square. So remember this, worst case time complexity of bubble sort is what? Order of n square.

So time complexity after 2 pass, after 3 pass, how the array will look like and the total number of swappings required. These are three important points related to bubble sort. Thank You.