PROGRAM TO COMPARE VARIOUS SEARCH TECHNIQUES.

#include<iostream.h>               //HEADER FILES
#include<time.h>
#include<fstream.h>
#include<math.h>

fstream file;
int record[30000],key[20000],valid,found;        //TO STORE DATA
long int comp=0,avgcomp;
float avgtime;

void seqsearch()                     //TO PERFORM SEQUENTIAL SEARCH
{
    comp=found=0;
    int i,j;
    for(i=0;i<valid;i++)
    {
        for(j=0;j<30000;j++)
        {
            if(record[j]==key[i])
            {
                //cout<<"\nfound "<<key[i]<<"  at "<<j;
                found++;
                break;
            }
            //else
            comp++;
        }
        //if(j==30000)
            //cout<<"\n not found**********";
    }
}

void binsearch()                  //TO PERFORM BINARY SEARCH
{
    comp=found=0;
    int top,mid,bot,i;
    for(i=0;i<valid;i++)
    {
        top=0;
        bot=29999;
        mid=(bot+top)/2;
        //cout<<"\n"<<mid;
        while(top<=bot)
        {
            //cout<<"\n"<<mid;
            if(record[mid]==key[i])
            {
                found++;
                comp++;
                //cout<<"\nfound"<<key[i]<<"  at "<<mid;
                break;
            }
            //else
            //{
                comp++;
                if(record[mid]>key[i])
                    bot=mid-1;
                else
                    top=mid+1;
                mid=(bot+top)/2;
            //}
        }
    }
}

void intersearch()         // TO PERFORM INTERPOLATION SEARCH
{
    comp=found=0;
    int top,mid,bot,i;
    for(i=0;i<valid;i++)
    {
        top=0;
        bot=29999;
        if(top!=bot)
            mid=top+(bot-top)*(key[i]-record[top])/(record[bot]-record[top]);
        while(bot-top>0)
        {
            if(record[mid]==key[i])
            {
                //cout<<"\nfound"<<key[i];
                comp++;
                found++;
                break;
            }
            else
            {
                comp++;
                if(top==mid||bot==mid)
                {
                    if(record[mid+1]==key[i])
                    {
                        found++;
                        //cout<<"\nfound"<<key[i];
                    }
                    //else
                    //    cout<<"\n notfound*******";
                    break;
                }
                if(record[mid]>key[i]&&bot!=mid)
                    bot=mid;
                else if(record[mid]<key[i]&&top!=mid)
                    top=mid;
                if(top!=bot)
                    mid=top+(bot-top)*(key[i]-record[top])/(record[bot]-record[top]);
            }
        }
    }
}

void robintersearch()   //TO PERFORM ROBUST INTERPOLATION SEARCH
{
    int top,bot,mid,min,max,position=0,k;
    int gap,probe;
    comp=found=0;
    for(k=0;k<valid;k++)
    {
        bot=29999;
        top=0;
        gap=sqrt(bot-top+1);
        while(top<bot)
        {
            probe=top+(bot-top)*((key[k]-record[top])/(record[bot]-record[top]));
            max=(probe>(top+gap))?probe:(top+gap);
            min=(bot-gap);
            mid=(min<max)?min:max;
            //cout<<"\n"<<probe<<"   "<<mid<<"          "<<min<<"         "<<max<<"           "<<top<<"           "<<bot;
            //comp=comp+2;
            if(mid>bot||mid<top)
            {
                //cout<<"\n not found!!!!!!!!!!!!!!!!!!!!!!";
                //comp++;
                break;
            }
            //comp++;
            if(key[k]==record[mid])
            {
                //cout<<"found "<<key[k]<<" at "<<mid<<endl;
                found++;
                comp++;
                break;
            }
            if(key[k]==record[mid-1])
                {
                    //cout<<"found "<<key[k]<<" at "<<mid-1<<endl;
                    found++;
                    break;
            }
            if(key[k]==record[mid+1])
                {
                    //cout<<"found "<<key[k]<<" at "<<mid+1<<endl;
                    found++;
                    break;
            }
            if((mid-top)<(bot-mid))
            {
                comp++;
                if(key[k]<record[mid])
                {
                    bot=mid-1;
                    gap=sqrt(bot-top+1);
                }
                else
                {
                    top=mid+1;
                    gap=2*gap;
                    if(gap>((bot-top)/2))
                        gap=(bot-top)/2;
                }               //end of if
            }
            else
            {
                comp++;

                if(key[k]>record[mid])
                {
                    top=mid+1;
                    gap=sqrt(bot-top+1);
                }
                else
                {
                    gap=2*gap;
                    bot=mid-1;
                if(gap>((bot-top)/2))
                        gap=(bot-top)/2;
                }              //end of if
            }                 // end of if
        }
    }
}


void main()                            //EXECUTION STARTS HERE
{
    int i,j,k;
    cout<<" \n\n     WAIT........................";
    file.open("records.txt",ios::in);
    for(i=0;i<30000;i++)              //READING DATA
        file>>record[i];
    file.close();

    file.open("keys.txt",ios::in);
    for(i=0;i<20000;i++)              //READING KEYS TO BE SEARCHED
        file>>key[i];
    file.close();

    file.open("sequence.txt",ios::out);   //SEQUENTIAL SEARCH
    long p,q;
    for(k=1;k<=200;k++)
    {
    valid=100*k;
    p=clock();
    seqsearch();
    q=clock();
    avgtime=(float)(q-p)/valid;
    avgcomp=comp/valid;
    file<<avgtime*1000<<"\t"<<avgcomp<<"\n";
    }
    file.close();

    file.open("binary.txt",ios::out);       //BINARY SEARCH
    for(k=1;k<=200;k++)
    {
    valid=100*k;
    p=clock();
    for(j=0;j<100;j++)
        binsearch();
    q=clock();
    avgtime=(float)(q-p)/valid/100;
    avgcomp=comp/valid;
    file<<avgtime*1000<<"\t"<<avgcomp<<"\n";
    }
    file.close();

    file.open("inter.txt",ios::out);       //INTERPOLATION SEARCH
    for(k=1;k<=200;k++)
    {
    valid=100*k;
    p=clock();
    for(j=0;j<1000;j++)
        intersearch();
    q=clock();
    avgtime=(float)(q-p)/valid/1000;
    avgcomp=comp/valid;
    file<<avgtime*1000<<"\t"<<avgcomp<<"\n";
    }
    file.close();

    file.open("robinter.txt",ios::out);     //ROBUST INTERPOLATION SEARCH
    for(k=1;k<=200;k++)
    {
    valid=100*k;
    p=clock();
    for(j=0;j<100;j++)
        robintersearch();
    q=clock();
    avgtime=(float)(q-p)/valid/100;
    avgcomp=comp/valid;
    file<<avgtime*1000<<"\t"<<avgcomp<<"\n";
    }
    file.close();

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s