Design and Analysis of Algorithms
| Program to sort list using selection sort. |
#include<iostream.h>
#include<conio.h>
void main()
{
int i,n,min,data[10],j,k,temp;
clrscr();
cout<<"\n Enter the no. of elements :";
cin>>n;
cout<<"\n Enter the elements of list";
for(i=1;i<=n;i++)
cin>>data[i];
for(k=1;k<=n;k++)
// finds the smallest element among data[k],
{
// data[k+1]…. Data[n] and put it to its corresponding position
min=data[k];
for(j=k+1;j<=n;j++)
{
if(data[j]<min)
{
min=data[j];
temp=data[k];
data[k]=min;
data[j]=temp;
}
}
}
cout<<"Sorted list is:";
for(i=1;i<=n;i++)
cout<<" "<<data[i];
getch();
}
| Output: |
Enter the no. of elements :5
Enter the elements of list 23
34
12
11
10
Sorted list is: 10 11 12 23 34
| Analysis of Selection Sort: |
The number of comparisons f(n) is independent of the original
order of the elements. There are n-1 comparisons in pass 1 to
find smallest element, there are n-2 comparisons during pass 2
to find the second smallest element and so on.
So, the complexity is for both worst case and average case is
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.