Bubble Sort in Java – Learn How to Implement with Example!

Sorting is a technique used by programmers around the world to arrange a given set of data in either ascending or descending order. Sorting is an integral part of data structure and a concept that cannot be neglected by programmers. In this article, we will take a look at one such sorting method known as Bubble sort in java.

What is Bubble sort?

Bubble sort is a stable sorting algorithm. You might ask what is a stable sort, it basically means that if there are two same elements in the data set, the order of the elements will be retained even after sorting.

Bubble sort repeatedly checks all the elements and swaps them to either take the largest element to the end or bring the smallest element upfront. The mechanism of bubble sort remains the same, but the sorting might vary depending on the user’s needs.

Why the name Bubble Sort?

The name given to this sort is very unique due to its unique feature. Bubble sort brings all the smaller elements to the top of the list and takes the largest element to the end of the list. We can say, just how bubbles float upwards as they are lighter than air, in bubble sort as well the lighter elements move to the top. Hence the name Bubble Sort.

Bubble Sort Algorithm:

Let us now see how Bubble sort works through a simple algorithm.

Algo_BubbleSort(A, N)
Step 1: Repeat for i in 0 to N
Step 2: Repeat for j in 0 to N-i-1
Step 3: Check If A[j] > A[j+1] then
Step 4: Swap A[j] and A[j+1]
Step 5: End Inner Loop
Step 6: End Outer Loop
Step 7: End Process

Dry Run of the above algorithm(Working Example):

Let us consider the following list: 3 4 1 2 6 8 7
We will check only one full iteration in detail to understand the working of Bubble sort.

Iteration 1:
a. Compare 3 and 4, Since 3<4, No swapping.
b. Compare 4 and 1, Since 4>1, Swapping needed: 3 1 4 2 6 8 7
c. Compare 4 and 2, Since 4>2, Swapping needed: 3 1 2 4 6 8 7
d. Compare 4 and 6, Since 4<6, No swapping.
e. Compare 6 and 8, Since 6<8, No swapping.
f. Compare 8 and 7, Since 8>7, Swapping needed: 3 1 2 4 6 7 8

This was just one iteration of the outer loop, this continues for N-1 times, where N is the size of the Array.
We can see from the above example clearly, how the largest element, i.e. 8, gets swapped to the end of the array.

Implementing Bubble Sort to Arrange in Ascending Order:

package com.DataFlair.Bubblesort;
class bubble_sort
{
    public static void main()
    {
        int i,j,temp,n=7;
        int array[]={3,4,1,2,6,8,7};
        for(i=0;i<n;i++)
        {
            for(j=0;j<n-i-1;j++)
            {
                if(array[j]>array[j+1])
                {
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        System.out.println("The array after sorting is: \n");
        for(i=0;i<n;i++)
        {
            System.out.print(array[i]);
        }
    }
}

Output:

Implementing Bubble Sort to Arrange in Descending Order:

package com.DataFlair.Bubblesort;
class bubble_sort
{
    public static void main()
    {
        int i,j,temp,n=8;
        int array[]={1,2,3,4,5,6,7,8};
        for(i=0;i<n;i++)
        {
            for(j=0;j<n-i-1;j++)
            {
                if(array[j]<array[j+1])
                {
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        System.out.println("The array after sorting is: \n");
        for(i=0;i<n;i++)
        {
            System.out.print(array[i]);
        }
    }
}

Output:

Time and Space Complexity of Bubble Sort:

• The Best Case time complexity of bubble sort is O(n)
• The Worst-Case time complexity of bubble sort is O(n^2)
• The Average Case time complexity of bubble sort is O(n^2)
• The Space Complexity of bubble sort is O(n)
• The Auxiliary Space Complexity of bubble sort is O(1)

Optimization of Bubble Sort:

Consider the following scenario:

The given array contains: 1 2 3 4 5 6 7 8

We can see that the array is already sorted, we don’t need to run the algorithm at all. But due to the mechanism of the algorithm, the algorithm will still execute N-1 times.

Now, consider a scenario where the array is sorted after the first or second iteration, in that case as well, the program will run N-1 times. This is a major issue with respect to time complexity. Let us see how we can fix the above program to get the optimal time complexity.

Optimized Program for Bubble Sort:

package com.DataFlair.Bubblesort;
class bubble_sort
{
    public static void main()
    {
        int i,j,temp,n=8;
        boolean flag= false;
        int array[]={1,2,3,4,5,6,7,8};
        for(i=0;i<n;i++)
        {
            flag = false;
            for(j=0;j<n-i-1;j++)
            {
                if(array[j]>array[j+1])
                {
                    flag=true;
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            if(flag==false)
            {
                System.out.println("The Array is Sorted");
                break;
            }
        }
        System.out.println("The array after sorting is: \n");
        for(i=0;i<n;i++)
        {
            System.out.print(array[i]);
        }
    }
}

Output:

As we can see, by adding a flag variable, we can optimize the bubble sort technique. The flag variable basically checks if there are any swapping operations happening in the inner loop and if there is no swapping, it means that the array is already sorted and we break out of the loop. This process reduces the complexity of the program by far and prevents unnecessary looping.

Use of Bubble Sort:

• Bubble sort is a simple yet useful sorting technique, it can sort a given set of data in linear time complexity for best-case scenarios.
• It can be used in greedy algorithms like Kruskal’s Algorithm to find the Minimal spanning tree in a graph.
• It can also be used in polygon filling algorithms, to detect very small errors in linear time complexity of 2n.

Advantages of Bubble Sort in Java:

1. Bubble sort is a basic sorting technique that requires a few lines of code and is very easy to understand.
2. It doesn’t use any complex algorithm techniques like Divide and Compare or Divide and Conquer.
3. It is a stable sort and thus the element’s memory location remains unchanged for equal value.

Disadvantages of Bubble Sort in Java:

1. For the average or worst-case scenario, bubble sort has a polynomial-time complexity of n^2 thus a data set with above a certain amount of elements will take forever to calculate even on a supercomputer.

2. Bubble sort works very slow on modern CPUs. It writes in the memory way more than any other sorting technique and produces even more cache misses.

Conclusion:

Bubble sort is the most commonly used algorithm for sorting due to its simplicity. In this article, we discussed in detail how bubble sort is implemented and how to optimize the bubble sort algorithm. We also discussed the uses of bubble sort and also the advantages and disadvantages of this sorting technique.