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.
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.
Example
Arr [] = {1, 2, 3, 4, 5, 6, 7}
As you can see the array is sorted already, but our algorithm(previous) will run all iterations and passes anyways
Arr [] = {1, 2, 3, 4, 5, 10, 7}
The above array is nearly sorted, just 10 out of place. However, in pass 1 itself the array will get sorted but previous algorithm will still run all the passes
As you can see the array is sorted already, but our algorithm(previous) will run all iterations and passes anyways
Arr [] = {1, 2, 3, 4, 5, 10, 7}
The above array is nearly sorted, just 10 out of place. However, in pass 1 itself the array will get sorted but previous algorithm will still run all the passes
How it is solved?
We can solve the above issue by bringing another boolean variable called swapped.
If in any pass no swapping happens, it means the array has become sorted and we do not need to run any further passes.
If in any pass no swapping happens, it means the array has become sorted and we do not need to run any further passes.
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
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Time Complexity
For Bubble Sort in C++
Best
O(n)
Average
O(n2)
Worst
O(n2)
Space Complexity
O(1)
Question 1. How many passes will be required for sorting the array. Arr[] = {1, 2, 4, 3} –
- 2
- 3
- 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} –
- 2
- 3
- 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 –
Asked in the following exams/interviews
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.
Login/Signup to comment
public class Main
{
public static void main(String[] args)
{
int a[]={7,9,3,0,2,1,5};
for(int i=0; i<a.length-1; i++){
for(int j=0; ja[j+1]){
//bubble sort
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(int i=0; i<a.length; i++){
System.out.print(a[i]+" ");
}
}
}
public class Main
{
public static void main(String[] args)
{
int a[]={8,7,6,5,4,3,2,1};
for(int i=0; i<a.length-1; i++){
for(int j=0; ja[j+1]){
//bubble sort
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(int i=0; i<a.length; i++){
System.out.print(a[i]+" ");
}
}
}
what is the time complexity of bubble sort for all case ?
https://prepinsta.com/cpp-program/bubble-sort/ visit this page Ritik. We hope this will resolve your queries