If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Table of Contents

## Bubble sort algorithm

`Bubble sort`

works by iterating first element to last element, comparing two adjacent elements and swapping them if they are not in correct order. Each iteration places next larger value to its correct place.#### Why bubble sort is called bubble sort or sinking sort(From wikipedia)

####
**Reason for being called Sinking sort**

**Reason for being called Sinking sort**

`sink`

to the bottom of the list####
**Reason for being called Bubble sort**

**Reason for being called Bubble sort**

`bubble`

up to the top of the list## Bubble sort Implementation

I have printed intermediate steps to understand it better:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
public class BubbleSortMain { /* * @author: Arpit Mandliya */ public static void main(String args[]) { int arr[]={100,20,15,30,5,75,40}; bubbleSort(arr); } public static int[] bubbleSort(int arr[]) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length-1-i; j++) { if(arr[j]>arr[j+1]) { int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } System.out.print("Iteration "+(i+1)+": "); printArray(arr); } return arr; } public static void printArray(int arr[]) { for (int i = 0; i <arr.length; i++) { System.out.print(arr[i]+" "); } System.out.println(); } } |

When you run above program, you will get following output:

Iteration 2: 15 20 5 30 40 75 100

Iteration 3: 15 5 20 30 40 75 100

Iteration 4: 5 15 20 30 40 75 100

Iteration 5: 5 15 20 30 40 75 100

Iteration 6: 5 15 20 30 40 75 100

Iteration 7: 5 15 20 30 40 75 100

You may notice that each iteration places next larger element to its correct place.

## Time Complexity:

**Best case:**

`O(n)`

**Average case:**

`O(n^2)`

**Worst case:**

`O(n^2)`