This C Program comapres among different searching algorithoms like
- Sequential(Unordered)
- Sequential(Ordered)
- Binary Search(Only for Ordered List)
- Interpollation Seach(Only For Ordered List)
This program doesn’t take any inputs.It takes random inputs and generates random numbers to be searched. And it outputs the time-complexity i.e number of comparisons of the search algorithoms.It also output a file in .xls format containning the data.
Code Snippet
- #include<stdio.h>
- #include<stdlib.h>
- #include<time.h>
- int seq_unord(int list[],int serch_el[],int no);
- int seq_ord(int ord_list[],int serch_el[],int no);
- int binary(int ord_list[],int serch_el[],int no);
- int intrpoll(int ord_list[],int serch_el[],int no);
- int unord_cnt=0,ord_cnt=0,bin_cnt=0,intr_cnt=0;
- int main()
- {
- int list[8192],serch_el[8192],ord_list[8192];
- int i=2,j,k,cnt=0,swap;
- FILE *fp;
- fp=fopen("data.xls","w");
- if(fp==NULL)
- {
- printf("\nFile cannot be openned.\n");
- exit(1);
- }
- fprintf(fp,"Number\tSeqUnord\tSeqOrd\tBinary\tIntrpoll");
- for(j=0;j<8192;j++)
- {
- list[j]=rand()%10000;
- ord_list[j]=list[j];
- }
- for(j=0;j<8192;j++)
- serch_el[j]=rand()%10000;
- i=2;
- while(i<=8192)
- {
- srand(time(0));
- for(j=0;j<i-1;j++)
- {
- for(k=j+1;k<i;k++)
- {
- if(ord_list[j]>ord_list[k])
- {
- swap=ord_list[j];
- ord_list[j]=ord_list[k];
- ord_list[k]=swap;
- }
- }
- }
- fprintf(fp,"\n%d\t%d\t%d\t%d\t%d",i,(seq_unord(list,serch_el,i)/i),(seq_ord(ord_list,serch_el,i)/i),(binary(ord_list,serch_el,i)/i),(intrpoll(ord_list,serch_el,i)/i));
- printf("\ni=%d,Total Searches--- Unorder=%d,Order=%d,Binary=%d,Interpollation=%d",i,unord_cnt,ord_cnt,bin_cnt,intr_cnt);
- i=i*2;
- }
- printf("\nYour data file has been processed and named 'data.xls'.\n");
- return 0;
- }
- int seq_unord(int list[],int serch_el[],int no)
- {
- int i,j,cnt=0;
- unord_cnt=0;
- for(i=0;i<no;i++)
- {
- for(j=0;j<no;j++)
- {
- cnt++;
- if(serch_el[i]==list[j])
- {
- unord_cnt++;
- break;
- }
- }
- }
- return(cnt);
- }
- int seq_ord(int ord_list[],int serch_el[],int no)
- {
- int i,j,cnt=0;
- ord_cnt=0;
- for(i=0;i<no;i++)
- {
- for(j=0;j<no;j++)
- {
- cnt++;
- if(serch_el[i]<=ord_list[j])
- {
- if(serch_el[i]==ord_list[j]) ord_cnt++;
- break;
- }
- }
- }
- return(cnt);
- }
- int binary(int ord_list[],int serch_el[],int no)
- {
- int i,first,last,mid,cnt=0;
- bin_cnt=0;
- for(i=0;i<no;i++)
- {
- first=0;last=no-1;
- while(first<=last)
- {
- mid=(first+last)/2;
- cnt++;
- if(serch_el[i]==ord_list[mid])
- {
- bin_cnt++;
- break;
- }
- else if(serch_el[i]<ord_list[mid]) last=mid-1;
- else first=mid+1;
- }
- }
- return (cnt);
- }
- int intrpoll(int ord_list[],int serch_el[],int no)
- {
- int i,first,last,mid,cnt=0,dn;
- intr_cnt=0;
- for(i=0;i<no;i++)
- {
- first=0;
- last=no-1;
- while((serch_el[i]>=ord_list[first] && serch_el[i]<=ord_list[last]) && first<=last)
- {
- cnt++;
- dn=ord_list[last]-ord_list[first];
- if(dn==0)
- mid=first;
- else
- mid=first+((serch_el[i]-ord_list[first])*(last-first)/dn);
- if (serch_el[i]==ord_list[mid])
- {
- intr_cnt++;
- break;
- }
- else if(serch_el[i]<ord_list[mid]) last=mid-1;
- else first=mid+1;
- }
- }
- return (cnt);
- }
For any Information we can contact me.Further detail discussion on this will be carried out later.
Any Suggestion is highly expected.
0 Responses to Different Number Seaching Algorithoms & Comparisons – C Programming(Sequential,Binary,Interpollation)