  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Bubble Sort in Java

Last Updated on September 22, 2023 by Mayank Dham 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=4) and j+1=1 (array=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 (4) < array (9) so we will not swap elements because the higher element (9) is already on the right side.
• For j=2, array (9) > array (1) so we will swap elements.
• For j=3, array (9) > array (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 (3) < array (4) so we will not swap elements.
• For j=1, array (4) > array (1) so we will swap elements.
• For j=2, array (4) < array (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 (3) > array (1) so we will swap elements.
• For j=1, array (3) < array (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 (1) < array (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