### Bubble Sort (Sinking sort)

**Given a array of integers, Sort it.**

Lets understand what is the input and the expected output.

Lets understand what is the input and the expected output.

###
**Algorithm**

In Bubble sort, each pair of adjacent items are compared and swapped if they are in the wrong order, as shown below.

**Lets see how it works:**Bubble sort iterates through a array, compares adjacent items and swap them if they are out of order. In each iteration, Largest item will be moved(bubble up) at its proper place.

So in above example, initially 40 and 20 will be compared. 40 > 20? Yes.

So 40 and 20 will be swapped.

Now, 40 and 60 will be compared, 40 > 60? No. So no need to swap and go ahead.

Now, 60 and 10 will be compared, 60 > 10? Yes. So 60 and 10 will be swapped.

Now, 60 and 50 will be compared, 60 > 50? Yes. So 60 and 50 will be swapped.

Now, 60 and 30 will be compared, 60 > 30? Yes. So 60 and 30 will be swapped and largest item 60 bubbled up at its proper place.

**Repeat the steps for remaining unsorted sub-array and each iteration through the array places the next largest value in its proper place.**

### Complexity

**1.**Time complexity of Bubble sort in

**Worst Case**is

**O(N^2),**which makes it quite inefficient for

sorting large data volumes.

O(N^2) because it sorts only one item in each iteration and in each iteration it has to compare n-i

elements.

**2.**Time complexity of Bubble sort in

**Best**

**Case**is

**O(N)**.

When the given data set is already sorted, in that case bubble sort can identify it in one single

iteration hence

**O(N)**.

It means while iteratng,

**from i=0 till**

**arr.length,**if there is no swapping required, then the array

is already sorted and stop there.

**3.**Bubble sort can identify when the list is sorted and can stop early.

**4.**Bubble sort is efficient for (quite) small data sets

**.**

**5.**It is Stable sort; i.e., does not change the relative order of elements with equal keys.

**6.**It takes O(1) extra space.

### Java Program for Bubble Sort

package sorting; public class BubbleSort { public static void main(String[] args) { new BubbleSort(); } public BubbleSort() { int[] arr=new int[]{2,5,3,1,4,5,1}; System.out.println("Before Sorting..."); printArray(arr); bubbleSort(arr); System.out.println("\nAfter Sorting..."); printArray(arr); } private void bubbleSort(int[] arr){ if(arr==null) return; boolean isSorted=true; for (int i = 0; i < arr.length-1; i++) { for (int j = 1; j < arr.length-i; j++) { if(arr[j-1] > arr[j]){ isSorted = false; int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } // Remember that a bubble sort will continue until no swaps have occurred, // which says that array is in proper sorted order. if(isSorted){ break; } } } private void printArray(int arr[]){ for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }

### You may also like to see

#### Merge Sort

#### Heap Sort

#### Selection Sort

#### Insertion Sort

**Enjoy !!!!**

**If you find any issue in post or face any error while implementing, Please comment.**

## Post a Comment