Bubble Sort

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

(adsbygoogle = window.adsbygoogle || []).push({});
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:#includeint 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{printf("Array[%d] = ",i);scanf("%d",&arr[i]);printf("\n");}for(i=0 ; i{for(j=0 ; 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{printf(" %4d",arr[i]);}return 0;}
The program output is tested on www.jdoodle.comOutput:Enter the number of elements in the Array: 6Enter the elements:Array[0] = 2Array[1] = 4Array[2] = 6Array[3] = 8Array[4] = 7Array[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 – nBest case : O (n2)Average case : O (n2)Worst case : O (n2)

(adsbygoogle = window.adsbygoogle || []).push({});
ThanksMukesh Rajput