Bubble Sort Optimization : Improvement in the best case and average case running time

 In previous article we have seen that  time complexity of bubble sort is o(n²) . This is same for all - worst case, average case or best case.

Consider a case, when array is already sorted. For this no swapping is done but we still have to continue with all (n-1) passes. Consider another case, when array will be sorted in 3rd or 4th  pass. Here we still have to continue with rest of passes.

What is Bubble Sort Optimization ?

If we can identify that the array is sorted then we should stop execution of further passes. This is optimization over original bubble sort algorithm.

#include<stdio.h>

void bubble_sort(int *arr, int n)

{

   int i, j, temp, flag = 0;

   for (i = 0; i < n-1; i++)

  {

      for (j = 0; j < n-i-1; j++)

      {

                   if( arr[j] > arr[j+1] )

                   {

                             flag = 1;

                   temp = arr[j];

                   arr[j] = arr[j+1];

                   arr[j+1] = temp;

                   }

       }

       if(flag == 0)

                     return;

   }

}

int main()

{

   int i, n, arr[8];

   printf("Enter the number of elements in the array :");

   scanf("%d",&n);

   printf("\n Enter the elements in the array :");

   for (i = 0; i < n; i++)

  {

       scanf("%d", &arr[i]);

  }

   printf("\n Array before sorting :");

   for (i = 0; i < n; i++)

  {

       printf("%d \t", arr[i]);

  }

  bubble_sort(arr,  n);

  printf("\n Array after sorting :");

  for (i = 0; i < n; i++)

  {

       printf("%d \t", arr[i]);

   }

return 0;

}

Time complexity of Optimized Bubble Sort :

In best case, time complexity of optimized bubble sort is o(n). In average case also, the performance of optimized bubble sort algorithm will be improved but in worst case (when all the passes will be performed), optimized bubble sort will be slower than original bubble sort.