How to Implement Bubble Sort in Java

Bubble sort is one of the simplest and easy to understand sort algorithm. It works by comparing each pair of adjacent elements in a list and swapping them if they are in wrong order. This swapping process is repeated for the entire set of elements again and again until no swaps are detected. At this point the whole list is sorted.

Since we may need to go through the entire list again and again, the worst case timing of the bubble sort is proportional to n*n where n is the number of elements in the list. Clearly bubble sort is an inefficient algorithm.

Understanding Bubble Sort

Bubble sort is easy to understand if explained with an example. Assume that we are given this list of numbers – [4,2,5,1]. The bubble sort works by going through the list and comparing the adjacent elements. Let us say we want the numbers to be sorted in the ascending order.

Pass 1 – We go through the entire list comparing adjacent elements and swapping them if needed, Initial – [4,2,5,1]
After first comparison – [2,4,5,1]
After second comparison – [2,4,5,1]
After third comparison – [2,4,1,5]

We start the next pass since there are no more elements to compare and we have detected a swap in the previous pass.

Pass 2 – We again through the entire list we have after the first pass,
Initial – [2,4,1,5]
After first comparison – [2,4,1,5]
After second comparison – [2,1,4,5]
After third comparison – [2,1,4,5]

We start the next pass since there are no more elements to compare and we have detected a swap in the previous pass.

Pass 3 – We again through the entire list we have after the second pass,
Initial – [2,1,4,5]
After first comparison – [1,2,4,5]
After second comparison – [1,2,4,5]
After third comparison – [1,2,4,5]

We start the next pass since there are no more elements to compare and we have detected a swap in the previous pass.

Pass 4 – We again through the entire list we have after the third pass,
Initial – [1,2,4,5]
After first comparison – [1,2,4,5]
After second comparison – [1,2,4,5]
After third comparison – [1,2,4,5]

This time we detected no swaps. This means that the list is sorted!

How to Implement Bubble Sort in Java

Following Java example program is a non optimized implementation of bubble sort. I have used the data set mentioned above for the program. The program has two implementations of bubble sort. The first one simply does the bubble sort and the second one shows the bubble sort iterations in the console. Also note that this Java example does in place sorting of the array destroying the original input.

import java.util.Arrays;

// Sorts a list of numbers using bubble sort
public class BubbleSortInJava {

    public static void main(String[] args) {
        int[] input = new int[] { 4, 2, 5, 1 };

        System.out.println("input:" + getArrayAsString(input));
        performBubbleSort(input);
        System.out.println("output:" + getArrayAsString(input));

        // Let us run the bubble sort in an animation for better understanding!
        input = new int[] { 4, 2, 5, 1 };
        System.out.println("Starting the sorting animation");
        performBubbleSortWithAnimation(input);
    }

    // Java example - Bubble sort
    // Please see the tutorial for more details of the algorithm   
    private static int[] performBubbleSort(int[] input) {
        int size = input.length;
        boolean swapped = false;
        do {
            swapped = false;
            for (int i = 1; i < size; i++) {
                if (input[i - 1] > input[i]) {
                    int temp = input[i];
                    input[i] = input[i - 1];
                    input[i - 1] = temp;
                    swapped = true;
                }
            }

        } while (swapped);
        return input;
    }

    // Convert an array to displayable string
    private static String getArrayAsString(int[] values) {
        return Arrays.toString(values);
    }

    // Perform bubble sort and display each step in the console
    private static int[] performBubbleSortWithAnimation(int[] input) {
        int size = input.length;
        boolean swapped = false;
        int phase = 1;
        do {
            swapped = false;
            System.out.println("phase " + phase + "-initial-" + getArrayAsString(input) + "   ");
            for (int i = 1; i < size; i++) {
                try {
                    Thread.sleep(1000);
                } catch (Exception ex) {
                }
                if (input[i - 1] > input[i]) {
                    int temp = input[i];
                    input[i] = input[i - 1];
                    input[i - 1] = temp;
                    swapped = true;
                }
                System.out.println("phase " + phase + "-comparison " + i + "-" + getArrayAsString(input) + "   ");
            }
            phase++;
        } while (swapped);
        return input;
    }
}

There are a number of variations of the Bubble sort which optimizes the sorting process. However if you are looking for an efficient algorithm, you should look at a different algorithm such as quick sort.

Do you have a programming problem that you are unable to solve? Please send us your problem and we will publish the solution! Please email us.

Leave a Reply