Bubble sort algorithm is the basic sorting algorithm with complexity of n^{2}

In each iteration, adjucent elements are compared with each other and if they are in reverse order, swapping is done.

If atleast one swapping is done in an iteration, next iteration will be exceuted. Iteration stops when there is no swap in current iteration.

After each iteration biggest elements from the unsorted part of elements is shifted to sorted part of elements.

Let's see it in action.

Assume that you want to sort the elements whose values are 4, 30, -3, 7 and 1. As I mentioned above, bubble sort will compare the adjecent elements and if they are in reverse order, swapping will happen.

In the example below, bigger element is shown in RED and smalled element is shown in GREEN. If element in GREEN is on right hand side and element in RED is in left hand side, swapping has to be done on those two elements.

As you can see above first we compare 4 and 30. Since they are in order there is no swapping.

Next we compare 30 and -3. Since they are not in order swapping will happen. Please note that in order to execute next iteration, atleast one swapping must be done in current iteration. Since one swapping has been done in this iteration, it is necessary to perfom next iteration. After swapping element order is now 4, -3, 30, 7 and 1.

Next we compare 30 and 7. Again these are not in order and hence swapping will be done. After swapping order is 4, -3, 7, 30 and 1.

Next we compare 30 and 1. Again these are not in order and hence swapping will be done. After swapping order is 4, -3, 7, 1 and 30.

As mentioned above, next iteration is required as 3 swapping has been done in current iteration.

At the end of the 1^{st} iteration the elements order is : -3, 4, 1, 7 and 30.

As you can see that largest element (30) is found and placed it at the last position and hence in 2^{nd }iteration we need not to consider it(30) for the comparison.

With the same logic, after the end of the 2^{nd }iteration the second largest element will be found and placed at the second last position and need not to consider last 2 elements for comparison in next iteration(if any). These elements are marked in BLACK. Only Elements in Blue, RED or GREEN need to consider for comparison in each iteration.

By this way in each iteration we need to compare one less pair of elements than the previous iteration.

Mathematically, if you have n elements to be sorted, total number of elements to be considered would be n + (n-1) + (n-2) + .....+1 = n*(n+1) / 2

I hope now you must have understood why the complexity of Bubble Sort is n^{2}

Let's come back to our example and see what happens in 2nd iteration.

first we compare 4 and -3. Since they are not in order swapping will happen. After swapping element order is now -3, 4, 7, 1 and 30. Again, one swapping is done, so it is required to go through next iteration.

Next we compare 4 and 7. Since they are in order ther will not be any swapping.

Next we compare 7 and 1. Again these are not in order and hence swapping will be done. After swapping order is -3, 4, 1, 7 and 30.

Now, we need not to compare 7 with 30 as 30 is the larget element and we already found it in last iteration and as suggested above there is no need to consider this element for comparison.

As mentioned above, next iteration is required as 2 swapping has been done in current iteration.

At the end of the 2^{nd} iteration the elements order is : -3, 1, 4, 7 and 30.

As you can see that two largest elements (7 and 30) were found and placed at the last two positions and hence in 3^{rd }iteration we need not to consider those elements for comparison. It also proves our logic of total number of comparison required to sort elements.

First we compare -3 and 4. Since they are in order, no swapping will happen.

Next we compare 4 and 1. Since they are not in order ther will be swapping of elements 4 and 1. As per the rule, next iteration is required as one swapping is done in this iteration. After swapping elements order is : -3, 1, 4, 7 and 30.

Now, we need not to compare 4 with 7 and rest of the elements in row as those are the largest element.

As mentioned above, next iteration is required as 1 swapping has been done in current iteration.

At the end of the 3r^{d} iteration the elements order was : -3, 1, 4, 7 and 30.

First we compare -3 and 1. Since they are not in order, swapping will happen.

There is no need to compare rest of the elements.

As per the rule we need to iterate one more time as swapping was done in last iteration. At the end of current iteration elements order is : -3, 1, 4, 7 and 30.

In the next iteration there will not be any swapping as you can see in the above image ( row 2) that all elements are now sorted and hence there is no swapping in next iteration. Iteration will stop at that point as there was no swapping.

I am sure you must have enjoyed this topic so far. Now let's attempt to implement the same logic in JAVA Code:

package com.Jwalant.model; public class Example { public void bubbleSort(int[] testArray) { boolean isSwapped = true; int i = 0; while (isSwapped ) { isSwapped = false; i++; for (int j = 0; j < testArray.length - i; j++) { if (testArray[j] > testArray[j + 1]) { int temp = testArray[j]; testArray[j] = testArray[j + 1]; testArray[j + 1] = temp; isSwapped = true; } } } } public static void main(String[] args) { int[] testArray = {4,30,-3,7,1}; System.out.print("Before Sorting :"); for(int i=0; i< testArray.length; i++) { System.out.print(" "+testArray[i]); } System.out.println(""); Example example = new Example(); example.bubbleSort(testArray); System.out.print("After Sorting : "); for(int i=0; i< testArray.length; i++) { System.out.print(" "+testArray[i]); } } }

If you have any question or feedback please send us via form provided below. I encourage you to participate in this tutorial and your suggestions will definitely be reviewed.

Java is a trademark of Oracle.

Apekshit.com is just for learning and testing. To improve basic understanding we provide some examples. We are constantly reviewing it to avoid errors, but we cannot warrant full correctness of all content.