# 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.

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

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription O(n)

O(n2)

O(n2)

## Space Complexity

O(1) ### Quiz Time Question 1. How many passes will be required for sorting the array. Arr[] = {1, 2, 4, 3} –

1. 2
2. 3
3. 4
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} –

1. 2
2. 3
3. 4
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 – ## 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. ### 4 comments on “Bubble Sort in Java”

• Satendra

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]+" ");
}
}
} 0
• Satendra

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]+" ");
}
}
} 1
• ritik

what is the time complexity of bubble sort for all case ? 0
• HelpPrepInsta 1