Bubble Sort
Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order. This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n2) where n is the number of items.
Bubble sort algorithm starts by comparing the first two elements of an array and swapping if Followed these condition, i.e., (1) if you want to sort the elements of array in ascending order and if the first element is greater than second then, you need to swap the elements but, (2) if the first element is smaller than second, you mustn't swap the element. Then, again second and third elements are compared and swapped if it is necessary and this process go on until last and second last element is compared and swapped. This completes the first step of bubble sort and the next time, we do not compare the last element of the first step and so on.
If there are n elements to be sorted then, the process mentioned above should be repeated n-1 times to get required result. But, for better performance, in second step, last and second last elements are not compared because, the proper element is automatically placed at last after first step. Similarly, in third step, last and second last and second last and third last elements are not compared and so on.
Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.
Best Case Time Complexity: O(n). Best case occurs when array is already sorted.
Auxiliary Space: O(1)
Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.
Sorting In Place: Yes
Stable: Yes
Algorithm
We assume list is an array of n elements. We further assume that swapfunction swaps the values of the given array elements.
begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort
/*C Program To Sort data in ascending order using bubble sort.*/
#include <stdio.h>
#include <conio.h>
void main()
{
int data[100],i,n,step,temp;
printf("Enter the number of elements to be sorted: ");
scanf("%d",&n);
for(i=0;i<n;++i)
{
printf("%d. Enter element: ",i+1);
scanf("%d",&data[i]);
}
for(step=0;step<n-1;++step)
{
for(i=0;i<n-step-1;++i)
{
if(data[i]>data[i+1])
/* To sort in descending order, change > to < in this line. */
{
temp=data[i];
data[i]=data[i+1];
data[i+1]=temp;
}
}
}
printf("In ascending order: ");
for(i=0;i<n;++i)
{
printf("%d ",data[i]);
}
getch();
}
Output :
Enter the number of elements to be sorted: 6
1. Enter element: 12
2. Enter element: 3
3. Enter element: 0
4. Enter element: -3
5. Enter element: 1
6. Enter element: -9
In ascending order: -9 -3 0 1 3 13
