Bubble Sort in Java

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(n2)
Best Case O(n)
Worst Case O(n2)
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.

Bubble Sort in Java

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.

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(n2), which is shit
  • When you have very large items then, it sucks even more as it becomes even more slow thanks to O(n2)
  • The algorithm will be slowest when the array is sorted by in reverse
  • Best Case : O(n), when its already sorted
Bubble Sort in Java meme

Time Complexity
For Bubble Sort in C++

Best

O(n)

Average

O(n2)

Worst

O(n2)

Space Complexity

O(1)

Quiz time

Quiz Time

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

  1. 2
  2. 3
  3. 4
  4. 5

(Wipro – AMCAT Test)

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} –

  1. 2
  2. 3
  3. 4
  4. 5

(TCS NQT)

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)

Check the answer below –

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.

Data Structures and Algorithm Learn Sorting

4 comments on “Bubble Sort in Java”