Bubble Sort Algorithm in Java with Example

Bubble Sort is the first sorting algorithm I learned during my college day, and after so many years it's the one I remember by heart. It's kind of weird that one of the most popular sorting algorithms is also one of the worst-performing sorting algorithms. Bubble sort's average-case performance is in O(n^2), which means as the size array grows, the time it takes to sort that array increases quadratically. Due to this reason, bubble sort is not used in production code, instead quick sort and merge sort are preferred over it. In fact, Java's own Arrays.sort() method, which is the easiest way to sort an array in Java also uses two pivot quicksort to sort primitive arrays and a stable mergesort algorithm to sort object arrays.

The reason for the slow performance of this algorithm is an excessive comparison and swapping since it compares each element of array to another and swaps if it is on the right side.

Due to quadratic performance, bubble sort is best suited for small, almost sorted lists e.g. {1, 2, 4, 3, 5}, where it just needs to do one swapping. Ironically, the best-case performance of bubble sort, which is O(n) beats quicksort's best-case performance of O(NlogN).

Someone may argue that why teaching an algorithm that poor performance, why not teach insertion or selection sort which is as easy as bubble sort and performs better. IMHO, the easiness of the algorithm depends upon the programmer as much as on the algorithm itself.

Many programmers will find insertion sort easier than bubble sort but again there will be a lot many who will find bubble sort easier to remember, including me. This is true, despite many of them have used insertion sort unknowingly in real life, e.g. sorting playing cards in hand.

Another reason for learning this sorting algorithm is for comparative analysis, how you improve algorithms, how you come up with different algorithms for the same problems. In short, despite of all its shortcomings, bubble sort is still the most popular algorithm.

In this tutorial, we will learn how bubble sort works, the complexity, and performance of bubble sort algorithm,  implementation, and source code in Java and a step-by-step example of bubble sort.

How Bubble Sort Algorithm works

If you are the one who focus on names, then you might have got an idea how bubble sort works. Just like a bubble comes up from water, in bubble sort smallest or largest number, depending upon whether you are sorting array on ascending or descending order, bubbles up towards start or end of the array.

We need at least N pass to sort the array completely and at the end of each pass one elements are sorted in its proper position. You can take first element from array, and start comparing it with other element, swapping where it's lesser than the number you are comparing.

You can start this comparison from start or from end, as we have compared elements from end in our bubble sort example. It is said that a picture is worth more than a thousand word and it's particularly true in case of understanding sorting algorithm. 

Let' see an step by step example to sort array using bubble sort, as I said after each pass largest number is sorted.

In this array, we start from index 0, which is 5 and starts comparing elements from start to end. So first element we compare 5 is 1, and since 5 is greater than 1 we swap them ( because ascending order sorted array will have larger number towards end).

Next we compare 5 to 6, here  no swapping because 6 is greater than 5 and it's on higher index than 5. Now we compare 6 to 2, again we need swapping to move 6 towards end. 

At the end of this pass 6 reaches (bubbles up) at the top of the array. In next iteration 5 will be sorted on its position and after n iteration all elements will be sorted. Since we compare each element with another, we need two for loops and that result in complexity of O(n^2).

FlowChart of Bubble Sort Algorithm

Another cool way to understand an algorithm is to draw it's flowchart. It will walk through each iteration in loop and how decisions are made during algorithm execution. Here is flowchart of our bubble sort algorithm, which complements our implementation of this sorting algorithm.

Here we have integer array {9, 7, 3, 6, 2} and start with four variable i, j, temp and array length which is stored in variable n. We have two for loop, outer loop runs from 1 to n-1. Our inner loop runs from n-1 to I.

Many programmer make mistake here, if you start outer loop with second element than make sure to use j>=i condition on inner loop, or if you start with first element e.g. i=0, make sure you use j>i to avoid ArrayIndexOutOfBound exception. Now we compare each element and swap them to move smaller element towards front of array.


As I said depending upon your navigation direction either largest element will be sorted at highest index in first pass or smallest element will be placed in lowest index. In this case, after first pass, smallest number will be sorted. This loop runs until j>=i after than it finishes and i becomes i + 1. This whole process repeats until outer loop is finished and that time your array is sorted.

In flowchart, a diamond box is used for decision making, which is equivalent of if-else statement in code. You can see here decision box is inside inner loop, which means we do N comparison in each iteration, totals to NxN comparisons.

Big O Complexity and Performance of Bubble Sort Algorithm

As I said before compared to other sorting algorithm like quicksort, merge sort or shell sort, bubble sort performs poorly. These algorithm has average case complexity of O(NLogN), while average case complexity of bubble sort O(n^2). 

Ironically in best case bubble sort do better than quicksort with O(n) performance.  Bubble sort is three times slower than quicksort or mergesort even for n = 100 but it's easier to implement and remember. 

Here is the summary of bubble sort performance and complexity :

• Bubble sort Worst case performance       O(n^2)
• Bubble sort Best case performance         O(n)
• Bubble sort Average case performance    O(n^2)

You can further explore insertion sort and selection sort, which also does sorting in similar time complexity. By the you can not only sort the array using bubble sort but ArrayList or any other collection class as well. Though you should really use Arrays.sort() or Collections.sort() for those purpose.

Bubble Sort Implementation in Java

here is the Java program to implement bubble sort algorithm using Java programming language. Don't surprise with import of java.util.Array, we have not used it's sort method here, instead it is used to print arrays in readable format. 

I have created a swap function to swap numbers and improve readability of code, if you don't like you can in-line the code in the swap method inside if statement of inner loop. 

Though I have used main method for testing, as it demonstrate better, I would suggest you to write some unit test case for your bubble sort implementation. 

If you don't know how to do that, you can see this JUnit tutorial.

import java.util.Arrays;
 
/**
* Java program to implement bubble sort algorithm and sort integer array using
* that method.
*
* @author Javin Paul
*/
public class BubbleSort{
 
   public static void main(String args[]) {
        bubbleSort(new int[] { 20, 12, 45, 19, 91, 55 });
        bubbleSort(new int[] { -1, 0, 1 });
        bubbleSort(new int[] { -3, -9, -2, -1 });

    }

    /*
     * This method sort the integer array using bubble sort algorithm
     */
    public static void bubbleSort(int[] numbers) {
        System.out.printf("Unsorted array in Java :%s %n",
                      Arrays.toString(numbers));

        for (int i = 0; i < numbers.length; i++) {
            for (int j = numbers.length -1; j > i; j--) {
                if (numbers[j] < numbers[j - 1]) {
                    swap(numbers, j, j-1);
                }
            }
        }

        System.out.printf("Sorted Array using Bubble sort algorithm :%s %n",
                Arrays.toString(numbers));
    }
    
    /*
     * Utility method to swap two numbers in array
     */
    public static void swap(int[] array, int from, int to){
        int temp = array[from];
        array[from] = array[to];
        array[to] = temp;
    }
 
}
 
 
Output
Unsorted array in Java : [20, 12, 45, 19, 91, 55]
Sorted Array using Bubble sort algorithm : [12, 19, 20, 45, 55, 91]
Unsorted array in Java : [-1, 0, 1]
Sorted Array using Bubble sort algorithm : [-1, 0, 1]
Unsorted array in Java : [-3, -9, -2, -1]
Sorted Array using Bubble sort algorithm : [-9, -3, -2, -1]

How to improve the Bubble Sort Algorithm?

In an interview one of the popular follow-up questions is how do you improve a particular algorithm, and Bubble Sort is no different than that. If you wrote bubble sort like the one we have shown here, the interviewer will definitely going to ask about how do you improve your bubble sort method.

 In order to improve any algorithm, you must understand how each step of that algorithm works, then only you will be able to spot any deficiency in code.

If you follow the tutorial, you will find that array is sorted by moving elements to their correct position. 

In worst case situation if array is reverse sorted then we need to move every element, this will require n-1 passes, n-1 comparison in each pass and n-1 exchanges, but how about best case if array is already sorted, our existing bubble sort method is still going to take n-1 pass, same number of comparison but no exchange.

If you observe carefully, you will find that after one passes through the array, the largest element will be moved to the end of the array, but many other elements also moved toward their correct positions, as bubbles move toward the water’s surface. 

By leveraging this property, you can deduce that during a pass, if no pair of consecutive entries is out of order, then the array is sorted. Our current algorithm is not taking advantage of this property.

If we track exchanges then we can decide whether additional iteration over array is needed or not. Here is an improved version of the Bubble Sort algorithm, which will only take 1 iteration and n-1 comparison in best case, when array is already sorted. 

This will also improve Bubble sort's average case performance, as compared to our existing method which will always take N - 1 passes.

    /*
     * An improved version of Bubble Sort algorithm, which will only do
     * 1 pass and n-1 comparison if array is already sorted. 
     */
    public static void bubbleSortImproved(int[] number) {        
        boolean swapped = true;
        int last = number.length - 2;

        // only continue if swapping of number has occurred
        while (swapped) {
            swapped = false;
            
            for (int i = 0; i <= last; i++) {
                if (number[i] > number[i + 1]) {
                    
                    // pair is out of order, swap them
                    swap(number, i, i + 1);
                    
                    swapped = true; // swapping occurred
                }
            }

            // after each pass largest element moved to end of array
            last--;
        }

    }

Now let's test this method for two inputs, one in which array is sorted (best case) and other on which only one pair is out of order. If we pass int array {10, 20, 30, 40, 50, 60} to this method,  initially will go inside while loop and make swapped=false. 

Then it will go inside for loop. when i =0 it will compare number[i] to number[i+1] i.e. 10 to 20 and check if 10 > 20, since it's not it will not go inside if block, and no swapping will be occurred. 

When i=1, it will compare 20 > 30 again no swapping, next when i =2 30> 40 which is false so no exchange again, next i =3 so 40> 50, which is again false, so no swapping. 

Now last pair comparison i=4, it will compare 50 > 60 again this is false, so control will not go inside if block and no exchange will be made. Because of that swapped will remain false and control will not go inside while loop again. So you know that your array is sorted just after one pass.

Now consider another example, where just one pair is out of order, let's say String array names = {"Ada", "C++", "Lisp", "Java", "Scala"}, here only one pair is out of order e.g. "Lisp" should come after "Java". Let's see how our improved bubble sort algorithm works here. 

In the first pass, the comparison will continue without exchange until we compare "Lisp" to "Java", here "Lisp".compareTo("Java") > 0 will become true, and swapping will occur, which means Java will go to the Lisp place, and Lisp will take Java's place. this will make boolean variable swapped=true.

Now in the last comparison on this pass, we compare "Lisp" to "Scala" and again no exchange. Now we will reduce the last index by 1 because Scala is sorted at the last position and will not participate further. 

But now swapped variable is true, so control will again go inside while loop, and for loop but this time no exchanged will be made so it will not take another pass. 

Our array is now sorted in just two passes compared to the N-1 pass of earlier implementation. This bubble sort implementation is much better and even performs better than the Selection sort algorithm in the average case because now sorting is not proportional to a total number of elements but only with number of pairs that are out-of-order.

By the way, to sort String array using Bubble Sort, you need to overload BubbleSortImproved() method to accept String[] and also need to use compareTo() method to compare two String objects lexicographically. Here is a Java program to sort String array using Bubble Sort :

import java.util.Arrays;

class BubbleSortImproved {

    public static void main(String args[]) {

        String[] test = {"Ada", "C++", "Lisp", "Java", "Scala"};
        System.out.println("Before Sorting : " + Arrays.toString(test));
        bubbleSortImproved(test);
        System.out.println("After Sorting : " + Arrays.toString(test));
    }

    /*
     * An improved implementation of Bubble Sort algorithm, which will only do
     * 1 pass and n-1 comparison if array is already sorted. 
     */
    public static void bubbleSortImproved(String[] names) {        
        boolean swapped = true;
        int last = names.length - 2;

        // only continue if swapping of number has occurred
        while (swapped) {
            swapped = false;
            
            for (int i = 0; i <= last; i++) {
                if (names[i].compareTo(names[i + 1]) > 0) {
                    
                    // pair is out of order, swap them
                    swap(names, i, i + 1);
                    
                    swapped = true; // swapping occurred
                }
            }

            // after each pass largest element moved to end of array
            last--;
        }

    }

    public static void swap(String[] names, int fromIdx, int toIdx) {
        String temp = names[fromIdx]; // exchange
        names[fromIdx] = names[toIdx];
        names[toIdx] = temp;
    }

}

Output:
Before Sorting : [Ada, C++, Lisp, Java, Scala]
After Sorting : [Ada, C++, Java, Lisp, Scala]

Which one is better Selection Sort vs Bubble Sort?

Though both Selection Sort and Bubble sort has the complexity of O(n^2) in the worst case. On average, we expect the bubble sort to perform better than the Selection sort because the bubble sort will finish sorting sooner than the selection sort due to more data movements for the same number of comparisons because we compare elements in pair on Bubble Sort.

If we use our improved implementation Bubble Sort then a boolean test to not enter on while loop when array gets sorted, will also help. 

As I said, The worst case of the bubble sort happens when the original array is in descending order, while in the best case, if the original array is already sorted, the bubble sort will perform only one pass whereas the selection sort will perform N - 1 pass. Given this, I think on average Bubble sort is better than Selection sort.


That's all about Bubble Sort in Java. We have learned how the bubble sort algorithm works and how do you implement it in Java. As I said, it is one of the simplest sorting algorithms and very easy to remember, but also it doesn't have any practical use apart from academics and in data structure and algorithm training classes.

Its worst-case performance is quadratic which means it is not suitable for a large array or lists. If you have to use bubble sort, it's best suited for a small, already sorted array in which case it has very few swapping and its performance is in O(n). If you love algorithms, you can see this problem of finding a cycle on a linked list.

And now it's quiz time: What is your favorite sorting algorithm in Computer science? Quicksort, Merge sort, Heap sort, Selection sort, Insertion sort, Radix sort, or  this one?