I want to count the number of comparisons in selection sort algorithm:
In the usual algorithm, i introduced a counting-variable cont
, and i have initialised it cont=0
.
The code is:
void selectionSort(int a[],int n)
{
int i,j,min,cont;
int tmp;
cont=0;
for(i=0;i<n;i++)
{
min=i;
for(j=i+1;j<=n;j++)
{
if(a[j]<a[min])
{min=j;
}
cont=cont+1;
}
tmp=a[i];
a[i]=a[min];
a[min]=tmp;
}
}
The problem is that when I apply this to a vector of dimension 4, say a[1]=2,a[2]=1,a[3]=4,a[4]=3
and then print("%d",cont)
, the output is 4200958
, which are way too much comparisons, so where is the error here?
EDIT: As @Arnold pointed out, i have corrected the mispelled initialisation of the vector, now the output is 4, which is incorrect as well, i'm expecting the result to be 6. So where is the error here?
*Below the full code edited:*
void selectionSort(int a[],int n)
{
int i,j,min,cont;
int tmp;
cont=0;
for(i=0;i<n;i++)
{
min=i;
for(j=i+1;j<=n;j++)
{
if(a[j]<a[min])
{min=j;
}
cont=cont+1;
}
tmp=a[i];
a[i]=a[min];
a[min]=tmp;
}
}
int main()
{
int a[4],cont;
cont=0;
a[0]=2;
a[1]=1;
a[2]=4;
a[3]=3;
selectionSort(a,4);
printf("%d",cont);
return 0;
}
Just change the second loop from:
for(j=i+1;j<=n;j++)
to:
for(j=i+1;j<n;j++)
you should remove the equal sign from the condition.