Bubble sort algorithm

`Bubble sort`

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

Bubble sort can be done in ascending order or descending order.

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

**Reason for being called Sinking sort**

The larger values might be regarded as heavier and therefore be seen to
progressively

`sink`

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

**Reason for being called Bubble sort**

The smaller values might be regarded as lighter and therefore be seen
to progressively

`bubble`

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

I have printed intermediate steps to understand it better:

public class BubbleSortMain {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 1: 20 15 30 5 75 40 100 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 the next larger element in its correct place.

## Time Complexity:

**Best case:**

`O(n)`

**Average case:**

`O(n^2)`

**Worst case:**

`O(n^2)`