Bubble sort

Bubble sort algorithm for sorting is one of the simplest but inefficient algorithms, which organize the sorting procedure by uniformly checking the two adjacent elements and accordingly adjusting their positions.

Time Complexity of Bubble Sort Algorithm

Bubble sort implementation in c

#include<stdio.h>

#define size 10
int main()
{
  int arr[size];
  int i,j,temp;
  printf("\nENTER %d VALUES: ",size);
  for(i=0;i<size;i++)
   scanf("%d",&arr[i]);
  for(i=0;i<size;i++)
  {
    for(j=size-1;j>i; j--)
    {
       if(arr[j]<arr[j-1])
       {
          temp=arr[j];
          arr[j]=arr[j-1];
          arr[j-1]=temp;
       }
    }
  }  
  printf("\nAFTER SORTING: ");
  for(i=0;i<size;i++)
   printf("%d ",arr[i]);
  return 0;
}

Analysis

In bubble sort, n-1 comparisons will be in the 1st pass, n-2 in the 2nd pass, n-3 in a 3rd pass and so on. So it’s very simple to calculate the number of comparisons. Total number of comparisons will be (n-1)+(n-2)+(n-3)+……+3+2+1. it’s a form of arithmetic progression series. So we can apply the formula

sum=n(n-1)/2 which is of O(n2)

The main advantage is the simplicity of the algorithm, the additional space requirement is only one temporary variable and it behaves as O(n) for a sorted array of the element.