Sorting Algorithm Bubble Sort : Implementing Bubble Sort Algorithm in C Program and Time Complexity of Bubble Sort

 What is Bubble Sort :

Bubble Sort is simple sorting algorithm. In case of arranging elements in ascending order, this algorithm sorts the array elements by repeatedly moving the largest element to the highest index position of array segment ( in pass 1), second largest element to second highest position (in pass 2) and so on. For this, in every pass two successive elements are compared and swapping is done if the first element is greater than second one.

Implementing Bubble Sort :

#include<stdio.h>

void bubble_sort( int arr[], int n)

{

       int i,  j, temp;

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

       {

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

             {

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

                    {

                          temp = arr[j];

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

                          arr[j+1] = temp;

                     }

             }

          }

}

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 Bubble Sort :

In bubble sort, (n-1) comparisons are made in 1st pass, (n-2) comparisons in 2nd pass, (n-3) comparisons in 3rd pass and so on. To compute the complexity of bubble sort, we need to calculate the total number of comparisons.

f(n) = (n-1) + (n-2) + (n-3) + . . . . . + 3 + 2 +1

       = n (n-1)/2

 Thus number of comparison is proportional to n² .

The time complexity of bubble sort is  o(n²).