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