Design and Analysis of Algorithms

Go Back to List

Program to sort list using Bubble sort.

 

#include<iostream.h>
#include<conio.h>
void main()
{
int a[10],i,j,n,temp;
clrscr();
cout<<"Enter number of elements:";
cin>>n;
cout<<"Enter the elements:";
for(i=0;i<n;i++)
{
cin>>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;
}
}
}
cout<<"\narray after sorting is:";
for(i=0;i<n;i++)
{
cout<<endl<<a[i];
}
getch();
}



 

Output:

Enter number of elements:5
Enter the elements:12
11
34
23
2

array after sorting is:
2
11
12
23
34

Analysis of Bubble Sort:

There are n-1 comparisons in the first pass, which places the largest element in the last position, there are n-2 comparisons in the second pass, which places the second largest element in the next-to-last position, and so on, thus,
f(n)= (n-1)+(n-2)+ …..+ 2+1= n(n-1)/2 = O(n2)

 

If any of you want  to submit your programs and contribute to site please mail us at:

citysuvidha@gmail.com

  Click here to have a look at  List of programs

You can download all the programs in a zip file also. For this you have to do one thing. Just register at the citysuvidha forum  and start any thread of any topic.  Once you start the thread and put your request, admin will automatically send you the desired zip file.