Bubble sort is a sorting algorithm that uses the swapping of elements to sort the array in either ascending or descending order. Bubble sort is the simplest and easy-to-understand sorting algorithm. In this article, we will learn more about bubble sort, the bubble sort algorithm java, and the time and space complexity of the bubble sort program in java.

## What is Bubble Sort Java?

The bubble sort algorithm compares adjacent elements and swaps them to sort the array. The bubble sort uses two for loops to sort the array. The first for loop (outer for loop) is used to traverse the array n times. The Second for loop (inner for loop) is used to traverse the array and swap elements if necessary.

## Bubble Sort Algorithm Java

Let’s understand how the bubble sort algorithm java works using an example and visualizing the algorithm. The process of sorting the array in ascending using the bubble sort algorithm java is given below.

Now Let’s see how n-1 (n=size of an array) array passes work on an array.

**First pass ( i=0)**

- First, we will run the inner loop for n-i-1 (5-0-1 = 4) times and we will compare each adjacent pair.
- For j=0, compare j=0 (array[0]=4) and j+1=1 (array[1]=3) here array[j]>array[j+1] so we will swap two elements because we want higher elements on the right side to sort an array.
- For j=1, array[1] (4) < array[2] (9) so we will not swap elements because the higher element (9) is already on the right side.
- For j=2, array[2] (9) > array[3] (1) so we will swap elements.
- For j=3, array[3] (9) > array[4] (5) so we will swap elements.
- After performing the first pass we can see that the last element of an array (9) is already at its right position so in further passes we will not touch that element.

**Second pass ( i=1)**

- In the second pass (i=1), we will run inner loop n-i-1 time ( 5-1-1 =3) which one less than the first pass it is because the last element is already sorted in the second pass so we will not consider the last element.
- For j=0, array[0] (3) < array[1] (4) so we will not swap elements.
- For j=1, array[1] (4) > array[2] (1) so we will swap elements.
- For j=2, array[2] (4) < array[3] (5) so we will not swap elements
- After the completion of the second pass, we can see that the last two elements of an array ( [5,9] ) are in their right position.

**Third pass ( i=2)**

- In the third pass ( i=2 ), we will run the inner loop n-i-1 (5-2-1 = 2) times.
- For j=0, array[0] (3) > array[1] (1) so we will swap elements.
- For j=1, array[1] (3) < array[2] (4) so we will not swap elements.
- After performing the third pass we can see that the last three elements ( [4,5,9] ) are in their right positions.

**Fourth pass ( i=3)**

- In the fourth pass (i=3 ), we will run the inner loop n-i-1 (5-3-1=1) times.
- For j=0, array[0] (1) < array[1] (3) so we will not swap elements.
- After performing the fourth pass we can see that our array is sorted.

Sorting happens in place in bubble sort java which means if there are two elements with the same values so after performing the bubble sort program in java the order of that two elements will be the same. Let’s understand this with an example array= [4,6,3,6,5] here two same elements are 6 at index 2 and 4 now after performing bubble sort array= [3,4,5,6,6] now two elements which is same are 6 at index 4 and 5 so element 6 at index 4 is element 6 at index 2 before performing sorting and element 6 at index 5 is element at index 4 before performing sorting.

## Bubble Sort Program in Java:-

class Prepbytes{ // method to implement bubble sort program in java public static void BubbleSort(int[] arr){ // find the length of an array int n=arr.length; // run outer for loop n-1 times for(int i=0;i<n-1;i++){ // run inner for loop n-i-1 times for(int j=0;j<n-i-1;j++){ // check if j th element is greater than j+1 th element if(arr[j]>arr[j+1]){ // swap j and j+1 th elements int tmp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=tmp; } } } } // method to print an array public static void DisplayArray(int[] arr,boolean before){ if(before==true){ System.out.print("Array Before Sorting: "); } else{ System.out.print("Array After Sorting: "); } for(int i=0;i<5;i++){ System.out.print(arr[i]+" "); } System.out.println(); } public static void main(String[] args) { // initialize an array int[] arr=new int[]{4,3,9,1,5}; // print array before performing bubble sort program in java DisplayArray(arr,true); // perform bubble sort program in java BubbleSort(arr); // print array after performing bubble sort program in java DisplayArray(arr,false); } }

**Output:-**

```
Array Before Sorting: 4 3 9 1 5
Array After Sorting: 1 3 4 5 9
```

There is one problem with the above bubble sort program in java when a given array is already sorted the above program will still finish all the two loops so the time complexity becomes O(n^2) though the array is already sorted. Let’s see how can we optimize the above bubble sort program in java.

### Optimized Bubble Sort Program in Java:-

We can observe one thing if our array is already sorted then no swap will be performed so we can use this observation to write an optimized bubble sort program in java.

class Prepbytes{ // method to implement bubble sort program in java public static void BubbleSort(int[] arr){ // find the length of an array int n=arr.length; // run outer for loop n-1 times for(int i=0;i<n-1;i++){ // variable to keep track of swap is performed or not boolean is_swap=false; // run inner for loop n-i-1 times for(int j=0;j<n-i-1;j++){ // check if j th element is greater than j+1 th element if(arr[j]>arr[j+1]){ // swap is performed so make is_swap true is_swap=true; // swap j and j+1 th elements int tmp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=tmp; } } // if no swap is performed then break the loop if(is_swap==false){ break; } } } // method to print an array public static void DisplayArray(int[] arr,boolean before){ if(before==true){ System.out.print("Array Before Sorting: "); } else{ System.out.print("Array After Sorting: "); } for(int i=0;i<5;i++){ System.out.print(arr[i]+" "); } System.out.println(); } public static void main(String[] args) { // initialize an array int[] arr=new int[]{4,3,9,1,5}; // print array before performing bubble sort program in java DisplayArray(arr,true); // perform bubble sort program in java BubbleSort(arr); // print array after performing bubble sort program in java DisplayArray(arr,false); } }

## Time complexity analysis of bubble sort java:-

**Best:- O(n)**when the given array is already sorted at that time program using only one loop.**Average:- O(n^2)**when the given array is not sorted.**Worst:- O(n^2)**when the given array is reverse sorted at that time we have to perform a swap for each comparison. So the total swaps performed will be n*(n-1)/2

## Auxiliary Space complexity of bubble sort java:-

**Auxiliary space complexity:- O(1)**it’s because we are not using any extra arrays to perform bubble sort java. We are only using variables so the space complexity is O(1) to perform the bubble sort algorithm java.

**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

Bubble Sort Program in Java

Fibonacci Series Program in Java

Calculator Program in Java

Fizzbuzz Program in Java

Matrix Program in Java

Stack Program in Java

Recursion Program in Java

Multiple Inheritance Program in Java