between merge sort and binary insertion sort which is more efficient?i know that theoritically both are nlogn search bt practically which will be better.that means if we plot the graph of number of comparison vs number of element in the list hose slope wll be slightly more than the other.and how will i count the comparison of binary insertion sort?for counting comparison in two different manner two different result are coming. if if i take the comparison of first and last then comparison of binary sort is greater than the merge sort bt if i take the comparison of the element with mid then merge has greater comparison.
this is my program
actually i am asked to plot graph for bubble,merge,insertion,binary insertion,shell sort when the number of element in the list is in the powe of 2 and list is randomly generated by rand function.pls help me i am really confused about this comparison thing,pls reply as soon as possible.tomorrow i have to show the program and i dont know what to do.
#include<stdio.h>
#include<stdlib.h>
int global;
int bubble(int p[],int);
void partition(int c[],int,int);
void sort(int a[],int,int,int);
int insert(int p[],int);
int binary(int p[],int);
int shell(int p[],int);
void pri(int p[],int);
void main()
{
global=0;
int i=0,n;
unsigned long int com;
int *b,*m;
char resp;
FILE *fp;
fp=fopen("sort.csv","w");
fprintf(fp,"n,bubble,merge,insertion,binary,shell,\n");
do
{
printf("pls enter the number of element int the array-> n\n");
printf("the value of n should in the power of 2");
scanf("%d",&n);
fprintf(fp,"%d,",n);
b=(int*)malloc(n*sizeof(int));
m=(int*)malloc(n*sizeof(int));
srand(time(0));
for(i=0;i<n;i++)
{
b[i]=rand()%100;
}
printf("the given array is \n");
for(i=0;i<n;i++)
{
printf("%d\t",b[i]);
}
printf("\n");
/* bubble sort */
printf("---------------bubble sort-------------- \n");
for(i=0;i<n;i++)
{
m[i]=b[i];
}
pri(b,n);
com=bubble(m,n);
fprintf(fp,"%d,",com);
/* mergesort */
printf("---------------mergesort---------------\n ");
for(i=0;i<n;i++)
{
m[i]=b[i];
}
pri(b,n);
partition(m,0,n-1);
printf(" the sorted array using merge sort is\n ");
for(i=0;i<n;i++)
{
printf("%d\t",m[i]);
}
printf("\n");
fprintf(fp,"%d,",global);
global=0;
/* insertion sort */
printf("---------------insertion sort---------------\n ");
for(i=0;i<n;i++)
{
m[i]=b[i];
}
pri(b,n);
com=insert(m,n);
fprintf(fp,"%d,",com);
/* binary insertion sort */
printf("---------------binary insertion sort--------------- \n");
for(i=0;i<n;i++)
{
m[i]=b[i];
}
pri(b,n);
com=binary(m,n);
fprintf(fp,"%d,",com);
/* shell sort*/
printf("---------------shell sort---------------\n");
for(i=0;i<n;i++)
{
m[i]=b[i];
}
pri(b,n);
com=shell(m,n);
fprintf(fp,"%d,",com);
fprintf(fp,"\n");
fclose(fp);
printf("enter ur choice y/n \n");
getchar();
resp=getchar();
getchar();
if(resp=='y')
fopen("sort.csv","a");
free(b);
free(m);
}
while(resp=='y');
}
void pri(int p[],int n)
{
printf("the original array is--------------------->\n");
int i;
for(i=0;i<n;i++)
{
printf("%d\t",p[i]);
}
printf("\n");
}
int bubble(int p[],int n)
{
int i,j,space;
unsigned long int com=0;
for(i=0;i<=n-2;i++)
{
for(j=0;j<=n-2-i;j++)
{
com++;
if(p[j]>p[j+1])
{
space=p[j];
p[j]=p[j+1];
p[j+1]=space;
}
}
}
printf(" the sorted array using bubble sort\n");
for(i=0;i<n;i++)
{
printf("%d\t",p[i]);
}
printf("\n");
return com;
}
int insert(int p[],int n)
{
unsigned long int com=0;
int i,j,temp;
for(i=1;i<n;i++)
{
temp=p[i];
for(j=i;j>0&&p[j-1]>temp;j--)
{
com++;
p[j]=p[j-1];
}
p[j]=temp;
com++;
}
printf("the sorted array using insertion sort is\n");
for(i=0;i<n;i++)
{
printf("%d\t",p[i]);
}
printf("\n");
return com;
}
int binary(int p[],int n)
{
int first,last,mid,i,j,temp;
unsigned long int comp=0;
for(i=1;i<n;i++)
{
temp=p[i];
first=0;
last=i-1;
while(first<=last)
{
comp++;
mid=(first+last)/2;
if(temp>p[mid])
first=mid+1;
else
last=mid-1;
}
comp++;
for(j=i;j>first;j--)
{
p[j]=p[j-1];
}
p[j]=temp;
}
printf("the sorted array using binary insertion sort is \n");
for(i=0;i<n;i++)
{
printf("%d\t",p[i]);
}
printf("\n");
return comp;
}
void partition(int c[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
partition(c,low,mid);
partition(c,mid+1,high);
sort(c,low,mid,high);
}
}
void sort(int a[],int low,int mid,int high)
{
int i,j,k,l;
int *b;
b=(int*)malloc((high+1)*sizeof(int));
l=low;
i=low;
j=mid+1;
while((l<=mid)&&(j<=high))
{ global++;
if(a[l]<=a[j])
{
b[i]=a[l];
l++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(l>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=l;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++)
{
a[k]=b[k];
}
free(b);
}
int shell(int p[],int n)
{
int span;
int j=0,k,temp;
unsigned long int com=0;
if(n!=1)
{
for(span=7;span>0;span=span-2)
{
for(j=span;j<n;j++)
{
temp=p[j];
for(k=j-span;k>=0&&p[k]>temp;k=k-span)
{
com++;
p[k+span]=p[k];
}
com++;
p[k+span]=temp;
}
}
}
printf(" the sorted array using shell sort is\n");
for(j=0;j<n;j++)
{
printf("%d\t",p[j]);
}
printf("\n");
return com;
}