bubble sort

Write a program to explain bubble sort. What is the worst case and best case time complexity of bubble sort?

In bubble sort method the list is divided into two sub-lists sorted and unsorted. The smallest element is bubbled from unsorted sub-list. After moving the smallest element the imaginary wall moves one element ahead. The bubble sort was originally written to bubble up the highest element in the list. But there is no difference whether highest / lowest element is bubbled. This method is easy to understand but time-consuming. In this type, two successive elements are compared and swapping is done. Thus, step-by-step entire array elements are checked. Given a list of ‘n’ elements the bubble sort requires up to n-1 passes to sort the data.

Implementation of Bubble sort in C language:

#include<stdio.h>

int main()

{

int i,n,temp,j,arr[25];

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

scanf("%d",&n);

printf("\nEnter the elements:\n");

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

{

printf("Array[%d] = ",i);

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

printf("\n");

}

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

{

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

{

if(arr[j]>arr[j+1]) //Swapping Condition is Checked

{

temp=arr[j];

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

arr[j+1]=temp;

}

}

}

printf("\nThe Sorted Array is:\n");

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

{

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

}

return 0;

}

The program output is tested on www.jdoodle.com

Output:

Enter the number of elements in the Array: 6

Enter the elements:

Array[0] = 2

Array[1] = 4

Array[2] = 6

Array[3] = 8

Array[4] = 7

Array[5] = 5

The Sorted Array is:

    2    4    5    6    7    8

Time Complexity of Bubble Sort :

The complexity of sorting algorithm is depends upon the number of comparisons that are made. Total comparisons in Bubble sort is: n ( n – 1) / 2 ≈ n 2 – n

Best case : O (n2)

Average case : O (n2)

Worst case : O (n2)

Thanks

Mukesh Rajput