Bubble Sort

Prerequisite:

Algorithm, Sorting, Asymptotic complexity(time complexity, space complexity)

Introduction:

Bubble sort may look same as insertion sort, because the outcome of the bubble sort looks same as insertion sort. In case of sorting in ascending order, Insertion sort will keep taking out the min value at end of the each iteration, whereas bubble sort will take out the max value. So both insertion and bubble sort look same.But there are few differences, when you look at the implementation.

Code:

 public int[] doBubbleSort(int[] ip) {  
      boolean isSwapped = false;  
      for(int i=1;i<ip.length;i++){  
           for(int j=0;j<ip.length-i;j++){  
                if(ip[j]>ip[j+1]){  
                     swap(ip, j, j+1);  
                     isSwapped = true;  
                }  
           }  
           if(!isSwapped){  
                break;  
           }  
      }  
      return ip;  
 }  

Complexity:

The time complexity of this sorting is O(n²) in a worst case scenario. In a best case scenario where the list is already sorted, the time complexity is O(n). The auxiliary memory/space is taken by this algorithm will never increase based on the number of elements. It always use the constant extra space. So the space complexity is O(1).

When/where to use:

Even though it has the interesting implementation and the fancy name, it will not be suitable for any case. We can say It's suitable for smaller array which has 10 or 15 elements, because of easy implementation. You can also use this algorithm, if the array is already sorted where the complexity is O(n). But in such cases, insertion sort is a better choice than this.