Bubble Sort Program in Java

In this article, we will write the bubble sort program in Java. We will understand the bubble sort algorithm, write the bubble sort program in Java, and will also cover various aspects of the bubble sort algorithm like its time and space complexity analysis, best case and worst case analysis, and stability analysis. So, let’s get started.

Bubble Sort

Bubble Sort is a sorting algorithm. This means that it is used to sort the elements of an array or a list in increasing or decreasing order. Bubble sort is a comparison-based sorting algorithm. This means that the sorting is performed by comparing the elements with one another. You might be wondering how can sorting happen without comparing the elements directly.

Well, there is another type of sorting called Linear sorting. This is not a comparison-based sorting. Count sort and radix sort, etc are some examples of linear sorting. However, it is out of the scope of the current discussion.

In bubble sort, on each iteration, we get the heaviest element at the end of the array. This means, the 1st iteration gives the maximum element, the second iteration gives the second maximum element, and so on (when we consider sorting in increasing order). The bubble sort algorithm is as follows.

Bubble Sort Algorithm:

  1. There will be N-1 iterations i.e. the iteration variable i varies as 0<= i < N-1. In each iteration, follow these steps:
    • Run a loop from 0 <= j < N-i+1.
    • In this loop, compare the adjacent elements i.e. array[j] and array[j+1]. If array[j] > array[j+1], the bigger element is before the smaller one in the array. So, swap them. Else, move further.
  2. After these N-1 iterations, the array will be sorted.

Let us demonstrate a dry run of these steps. So, consider the array shown below.

We will now sort this array using bubble sort. So, the first iteration and its steps are shown below.

So, in the first pass of the first iteration, we compare the first 2 elements. Since 5 is smaller than 9 i.e. the smaller element is on the left and larger on the right, the elements are in sorted positions with respect to each other. Hence, we don’t swap them.

Next, we compare 9 and 8. Since 9 is greater than 8, we will swap these elements and now 8 will come before 9.

Next, 9 and 2 are compared and again 9 gets swapped with 2. Then we compare 9 and 1. Since 9 is greater than 1, we swap them. Now, we can see that the largest element of the array i.e. 9 is at its sorted position i.e. at the last of the array. This will happen in every iteration.

So, we have established a fact that in the ith iteration of bubble sort, the ith largest element will move to the ith position from the back of the array i.e. its sorted position.

This was just the 1st iteration. Let us do one more iteration. The second iteration swaps are shown below.

So, the box around the last element i.e. 9 shows that it is already in its sorted position and no element will be compared to 9. So, the first 2 elements i.e. 5 and 8 are compared. Since they are in sorted positions with respect to each other, no swaps take place.

Next, we compare elements 8 and 2. Since 8 is larger than 2, the swap takes place. Then, 8 and 1 are compared and since 8 is greater than 1, swapping takes place and 8 goes to the second last position of the array.

So, we got the second largest element at the second last position of the array in the second iteration of bubble sort.

This is how the complete bubble sort algorithm will continue for 4 iterations (as there are 5 elements and the number of iterations = N-1 = 5-1=4). The rest of the iterations are shown below.

So, we can see that after 4 iterations, the array got sorted. So, now that we have understood the logic, let us write the bubble sort program in Java.

Bubble Sort Program in Java

import java.util.*;

public class Main {

    public static void bubbleSort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++)
            for (int j = 0; j < n - i - 1; j++)
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
    }
    
    public static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] arr = {5,9,8,2,1};
        bubbleSort(arr);
        for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Time Complexity of Bubble Sort Program in Java:

The time complexity of the above program is O(n2) where n is the number of elements. This is because we are using a nested loop. The outer loop runs for n-1 iterations and the inner loop runs for n-i+1 iterations.

Space Complexity of Bubble Sort Program in Java:

Since we have not used any extra space, the auxiliary space used will be O(1).

Bubble Sort Program in Java – Optimized Version

We cannot improve the time complexity of the bubble sort algorithm. It will remain O(n2). However, we can improve something about this algorithm. The bubble sort algorithm as per the program shown above will complete n-1 iterations even if the array is sorted. However, we can modify it to just do 1 iteration, and in 1 iteration, if no swaps are made, this means that the array is sorted. So, we will not perform any more iterations. This change is shown in the program below.

Bubble Sort Program in Java – Optimized Version

import java.util.*;

public class Main {

    public static void bubbleSort(int arr[]) {
        int n = arr.length;
        boolean flag = false;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++)
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            if(flag == false) break;
        }
    }
    
    public static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] arr = {5,9,8,2,1};
        bubbleSort(arr);
        for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Time Complexity of Optimized Bubble Sort Program in Java:

The time complexity is still the same. However, the best-case time complexity has improved, but the overall time complexity is still O(n2).

Space Complexity of Optimized Bubble Sort Program in Java:

The space complexity is also the same i.e. O(1).

Best Case of Bubble Sort Program in Java

From the optimized version of bubble sort, we can say that the best case of the bubble sort is when the array is already sorted as then we only have to perform 1 iteration on the array. Hence, the best case of bubble sort is when the input array is already sorted and the best case time complexity is O(N) where N is the number of elements.

Worst Case of Bubble Sort Program in Java

The worst case of the Bubble Sort algorithm is when the array is reverse sorted. This is because if the array is reverse sorted i.e. if we want to sort in ascending order and the array is in descending order or vice versa, then the bubble sort algorithm will perform the maximum number of comparisons and swaps. So, the worst case of the bubble sort algorithm is if the array is reverse sorted and the worst case time complexity is O(n2).

Is Bubble Sort Stable?

Yes, Bubble sort is a stable algorithm. What do we mean by stability? Consider the array shown below.

There are two 2s in the array. One is named 2a and the other as 2b. Before sorting, element 2a is before element 2b. After sorting also, we want 2a to be before 2b. If a sorting algorithm is able to maintain the order between the equal elements as it was before sorting, then that algorithm is a stable sorting algorithm.

You can try to sort this array using bubble sort. You will find that bubble sort is a stable algorithm.

So, these were the most important points about the bubble sort algorithm. We hope that you understood the Bubble Sort program in Java and liked the discussion. We hope to see you again soon at PrepBytes.

Other Java Programs

Java Program to Add Two Numbers
Java Program to Check Prime Number
Java Program to Check Whether a Number is a Palindrome or Not
Java Program to Find the Factorial of a Number
Java Program to Reverse a Number
Java Program to search an element in a Linked List
Program to convert ArrayList to LinkedList in Java
Java Program to Reverse a linked list
Java Program to search an element in a Linked List
Anagram Program in Java
Inheritance Program in Java
Even Odd Program in Java
Hello World Program in Java
If else Program in Java
Binary Search Program in Java
Linear Search Program in Java
Menu Driven Program in Java
Package Program in Java
Leap Year Program in Java
Array Programs in Java
Linked List Program in Java
String Programs in Java
Star Program in Java
Number Pattern Program in Java
For Loop Program In Java
Pattern Program in Java
String Palindrome Program in Java
Thread Program in JAVA
Java Scanner Program
While Loop Program in Java

Leave a Reply

Your email address will not be published. Required fields are marked *