bubble sort

Bubble sort is a simple sorting algorithm in which adjacent elements are compared and swapped if they are not in increasing order. This algorithm works with time complexity of Ο(n2) where n is the number of items.

working of bubble sort:

lets take an example: let our array be a[5]= {11,19,7,9,2}

 Starting from the first index, compare the first and the second elements.If the first element is greater than the second element, they are swapped.

Now, compare the second and the third elements. Swap them if they are not in order.

The above process goes on until the last element. the largest element comes at the end of the array

The same process goes on for the remaining phases. After each iteration, the largest element among the unsorted elements is placed at the end.

the element 2 doesnt require any sorting as it is already placed in sorted position
so, we see that if the number of elements in array is n we will require n-1 phases 
In each phases, the comparison takes place up to the last unsorted element, so we will required n-1-i comparations ( where n is number of elements in array , i is for phases )

The array is sorted when all the unsorted elements are placed at their correct positions.

implementation: 

void bubbleSort(int arr[], int n)  
{  
      
   for (int i = 0; i < n-1; i++)      
   { 
    // Last i elements are already in place  
    for (int j = 0; j < n-i-1; j++)  
      {
         if (arr[j] > arr[j+1])  
         { 
         // swap arr[j+1] and arr[j] 
          int temp = arr[j]; 
          arr[j] = arr[j+1]; 
          arr[j+1] = temp; 
         }   
      }
   }
}

time complexity :O(n^2)

Optimized Implementation:
The above function always runs O(n^2) time even if the array is sorted. It can be optimized by stopping the algorithm if inner loop didn’t cause any swap (ie. it is already sorted before n-1 phases)

void bubbleSort(int arr[], int n)  
{  
    int i, j;  
   for (i = 0; i < n-1; i++)      
   { 
       int yes=0;
    // Last i elements are already in place  
    for (j = 0; j < n-i-1; j++)  
      {
         if (arr[j] > arr[j+1])  
           { 
           // swap arr[j] and arr[j+1] 
            temp = arr[j]; 
            arr[j] = arr[j + 1]; 
            arr[j + 1] = temp; 
            yes=1; 
          }
      }
      if(yes==0)
      break;
   }
}