Bubble Sort in Java

June 18, 2022

What is Bubble Sort in Java?

Bubble Sort is the elementary sorting algorithm for sorting various data structures. It is a comparison-based sorting algorithm in which each element is compared with the next element, and is swapped if those elements are not in the correct order.

The algorithm starts with comparing the first pair of elements.
If the first element is smaller than the second element, then the elements are swapped
This algorithm is not suitable for large data sets

Time Complexity	O(n²)
Best Case	O(n)
Worst Case	O(n²)
Space Complexity	O(1)
Avg. Comparisons	n(n-1)/2

Implementation of bubble sort in Java

First, we will take starting two elements from the list.
Then we will compare those elements.
If these elements are found in unsorted order we will sort them.
Else we will compare next to elements.
We will repeat the previous steps until we get our sorted array.

Let’s take an example, we have a list of number stored in array

Pass 1

( 28 6 4 2 24 ) -> ( 6 28 4 2 24 ) : Swapped 28 & 6 since 28 > 6
( 6 28 4 2 24 ) -> ( 6 4 28 2 24 ) : Swapped 28 & 4 since 28 > 4
( 6 4 28 2 24 ) -> ( 6 4 2 28 24 ) : Swapped 28 & 2 since 28 > 2
( 6 4 2 28 24 ) -> ( 6 4 2 24 28 ) : Swapped 28 & 24 since 28 > 24

This is called as bubble sort as you can see in each pass we get the largest element, which pushes (bubbles) towards the right always. Just like in a soda the largest bubble traverse to top of first.

Algorithm for Bubble Sort in Java

Step1: Repeat step 1 to 4 for i=0 to n
Step2: For j=0 to n
Step3: if(arr[j]>arr[j+1]
Step4: swap(arr[j],arr[j+1])
Step5: End

Bubble Sort (Method 1)

Run

// Time Complexity : O(N^2)
// Space Complexity : O(1)
class Main
{
    static void bubbleSort(int a[])
    {
        int len = a.length; // calculating the length of array
        for (int i = 0; i < len-1; i++)
            for (int j = 0; j < len-i-1; j++) 
                if (a[j] > a[j+1]) //comparing the pair of elements
                {
                    // swapping a[j+1] and a[i]
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
    }

    /* Prints the array */
    static void printArray(int a[])
    {
        int len = a.length;
        for (int i = 0; i < len; i++)
            System.out.print(a[i] + " "); //printing the sorted array

        System.out.println();
    }

    // Main method to test above
    public static void main(String args[])
    {
        int arr[] = {64, 34, 25, 12, 22, 11, 90};

        bubbleSort(arr);//calling the bubbleSort function

        System.out.println("Sorted array");

        printArray(arr); //calling the printArray function
    }
}

Output

Sorted array
11 12 22 25 34 64 90

Bubble Sort Method 2 (Optimized)

The issue with previous algorithm was that it will always run all passes and iterations. Even if the arrays are already sorted, nearly sorted or not sorted.

We need to optimize the previous algorithm so that if the array becomes sorted at some time. We do not implement the algorithm further and print the array right then and ther.

Example Arr [] = {1, 2, 3, 4, 5, 6, 7}
As you can see the array is sorted already, but our algorithm(previous) will run all iterations and passes anyways

Arr [] = {1, 2, 3, 4, 5, 10, 7}
The above array is nearly sorted, just 10 out of place. However, in pass 1 itself the array will get sorted but previous algorithm will still run all the passes

How it is solved? We can solve the above issue by bringing another boolean variable called swapped.

If in any pass no swapping happens, it means the array has become sorted and we do not need to run any further passes.

Method 2 (Code in Java Optimized)

Run

// Time Complexity : O(N^2)
// Space Complexity : O(1)
class Main
{
    static void bubbleSort(int a[])
    {
        int len = a.length; // calculating the length of array
        for (int i = 0; i < len-1; i++) {

            // for optimization when array is already sorted & no swapping happens
            boolean swapped = false;
            for (int j = 0; j < len - i - 1; j++) 
            { 
                if (a[j] > a[j + 1]) //comparing the pair of elements
                {
                    // swapping a[j+1] and a[i]
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    // swapping happened so change to true
                    swapped = true;
                }
            }

            // if no swaps happened in any of the iteration
            // array has become sorted so stop with the passes
            if(swapped == false)
                break;

        }
    }

    /* Prints the array */
    static void printArray(int a[])
    {
        int len = a.length;
        for (int i = 0; i < len; i++)
            System.out.print(a[i] + " "); //printing the sorted array

        System.out.println();
    }

    // Main method to test above
    public static void main(String args[])
    {
        int arr[] = {1, 2, 3, 4, 5, 6, 7};

        bubbleSort(arr);//calling the bubbleSort function

        System.out.println("Sorted array");

        printArray(arr); //calling the printArray function
    }
}

Advantages of using Bubble Sort

LOL !!!! None, but if you still have to know then they could be –

Bubble sort would need lesser memory then other sorting techniques.
Even Noob Programmers can understand it

Why Bubble sort Sucks !!!

Its, time complexity is O(n²), which is shit
When you have very large items then, it sucks even more as it becomes even more slow thanks to O(n²)
The algorithm will be slowest when the array is sorted by in reverse
Best Case : O(n), when its already sorted

Time Complexity
For Bubble Sort in C++

Best

O(n)

Average

O(n²)

Worst

O(n²)

Space Complexity

O(1)

Quiz Time

Question 1. How many passes will be required for sorting the array. Arr[] = {1, 2, 4, 3} –

(Wipro – AMCAT Test)

Solution & Explanation

In bubble sort even if the array of n items is sorted completely the number of passes required is n – 1. Thus answer is C that is 3 passes.

Unless it is specified in the question that the algorithm used is optimized bubble sort answer remains the same.

In the case of optimized bubble sort the answer will be 2 passes as –

Arr = {1, 2, 4, 3}
After Pass 1 : {1, 2, 3, 4} (Swapped Yes)
After Pass 2: {1, 2, 3, 4} (Swapped No)

Since, there was no swapping in pass 2. We realized the array was already sorted

Question 2. How many iterations will be required for sorting the array? Arr[] = {10, 50, 40, 30, 70, 60} –

(TCS NQT)

Solution & Explanation

In bubble sort of n items there will be (n-1) passes in each passes the number of iterations will be –

Pass 1 – (n-1)
Pass 2 – (n-2)
Pass 3 – (n-3)
so on …
Pass (n-1) – 1

So total number of iterations –

(n-1) + (n-2) + (n-3) ….. + 3 + 2 + 1

The above looks like the sum of first n-1 numbers.

We know that sum of first n natural numbers can be found out using formula – n(n+1)2

Replace n with n-1 the answer will be (n-1)n/2.

So for n = 6*5/2 = 15 iterations

Question 2. How will the array look like after Pass 3 iteration 3 –

Arr = {10, 6, 2, 18, 16, 4, 8, 14}

FUB Question asked in TCS NQT.

Fill up the box.

(TCS NQT)

Solution & Explanation

Check the answer below –

Asked in the following exams/interviews

AMCAT(Automata Fix) Cocubes Cisco Interview Capgemini Interview Amazon Interview TCS Interview Infosys Interview IBM Interview

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Classification of Sorting Algorithms
Bubble Sort – C | C++ | Java
Insertion Sort – C | C++ | Java
Selection Sort – C | C++ | Java
Merge Sort – C | C++ | Java
Quick Sort – C | C++ | Java
Counting Sort – C | C++ | Java
Radix Sort – C | C++ | Java
Heap Sort – C | C++ | Java

4 comments on “Bubble Sort in Java”

Satendra
public class Main
{
public static void main(String[] args)
{
int a[]={7,9,3,0,2,1,5};
for(int i=0; i<a.length-1; i++){
for(int j=0; ja[j+1]){
//bubble sort
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;

}
}
}
for(int i=0; i<a.length; i++){
System.out.print(a[i]+" ");
}
}
}

0

Log in to Reply
Satendra
public class Main
{
public static void main(String[] args)
{
int a[]={8,7,6,5,4,3,2,1};
for(int i=0; i<a.length-1; i++){
for(int j=0; ja[j+1]){
//bubble sort
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;

}
}
}
for(int i=0; i<a.length; i++){
System.out.print(a[i]+" ");
}
}
}

1

Log in to Reply
ritik
what is the time complexity of bubble sort for all case ?

0

Log in to Reply

HelpPrepInsta
https://prepinsta.com/cpp-program/bubble-sort/ visit this page Ritik. We hope this will resolve your queries

0

Log in to Reply

Bubble Sort in Java

What is Bubble Sort in Java?

Implementation of bubble sort in Java

Pass 1

Algorithm for Bubble Sort in Java

Bubble Sort (Method 1)

Output

Bubble Sort Method 2 (Optimized)

Method 2 (Code in Java Optimized)

Advantages of using Bubble Sort

Why Bubble sort Sucks !!!

Time Complexity For Bubble Sort in C++

Best

Average

Worst

Space Complexity

Quiz Time

Asked in the following exams/interviews

Sorting

4 comments on “Bubble Sort in Java”

Time Complexity
For Bubble Sort in C++