Bubble Sort

Bubble Sort (Sinking sort)

---

Given a array of integers, Sort it.
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 javabypatel;

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

Quick Sort

Enjoy !!!! 

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