BUBBLE SORT

BUBBLE SORT:

It is the simpler and well known sorting technique. It is less efficient for large amount of data as its average and worst case complexity is high. Bubble sort is stable and adaptive.In this sorting technique, we need to compare and swap the adjacent elements of the array till we get whole array sorted.i

Worst case:O(n2)

Average case :O(n2)

Best case:O(n)

e.g. To sort  8,5,2,1

8 , 5 , 2 , 1               8>5, swap(8,5)
5 , 8 , 2 , 1               8>2, swap(8,2)
5 , 2 , 8 , 1               8>1, swap(8,1)            

5 , 2 , 1 , 8               5>2, swap(5,2)
2 , 5 , 1 , 8               5>1, swap(5,1)

2 , 1 , 5 , 8               2>1, swap(2,1)

1 , 2 , 5 , 8               SORTED ARRAY

ALGORITHM:

• Input the array, a[]
• while (i<=n-1)
  while(j<(n-j-1)
  Compare a[j] with a[j+1] and swap as per requirement
  Increment j
  [END OF INNER LOOP]
  Increment i
  [END OF OUTER LOOP]

C SOURCE CODE:

#include<stdio.h>
#include<conio.h>   
void main() 
{ 
int a[100], n, i, j, temp;   
printf("Enter number of elements\n"); scanf("%d", &n);   
printf("Enter %d elements\n", n);   

for (i = 0;i<n; i++)
scanf("%d", &a[i]);

for (i=0; i<(n-1);i++)
{
for (j=0;j<(n-i-1); j++)
{
if (a[j]<a[j+1])
{ 
temp=a[j]; 
a[j]=a[j+1]; 
a[j+1]=temp; 
} 
} 
}   
printf("Sorted array\n");   
for (i=0;i<n;i++ ) 
printf("%d\t",a[i]);   
getch(); 
}