Go ahead

Go ahead
Logic doesn't explain everything

Computer Algorithm Lab

1.Write a program that writes some number randomly in a file and then sorts these numbers using bubble sort, selection sort and insertion sort and compute the running time for each sorting procedure.
  
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;

int main()
{
    FILE *fp;  // File declaration
    int n,r1,r2,choose,test;
    double t1,t2,t3,t4,t5,t6;
    cout<<"\nHow many tests ? ";    // Prompt for no.of data test
    cin>>test;
    cout<<"\nRandom numbers ranging from _ to _ ";  //Prompt for range of random numbers
    cin>>r1>>r2;
    fp=fopen("D:\\lab_1.txt","w+");  //Opening file in 'D' Drive
    choose=1;
    while(choose<=test){
    cout<<"\nHow many numbers do you want to sort? ";//Prompt for the no. of data in each test
    cin>>n;
    int NUM[n],a[n],b[n],i,p,t,j,value,min;
    srand(time(0));
    fprintf(fp,"\nGenerated Random Numbers are:\n\n");
    for(i=0;i<n;i++){
        NUM[i]=(r1+rand()%(r2-r1));
        fprintf(fp,"%d\t",NUM[i]);
        a[i]=NUM[i];
        b[i]=NUM[i];
    }
    fprintf(fp,"\n");
    //Bubble sort and recording the start time
    t1=clock();
    for(i=0;i<n;i++){
        for(p=0;p<n-i;p++){
            if(NUM[p]>NUM[p+1]){
                t=NUM[p];
                NUM[p]=NUM[p+1];
                NUM[p+1]=t;
            }
        }
    }
    t2=clock();//recording the end time
    fprintf(fp,"\nAfter sorting by Bubble sort:\n\n");
    for(i=0;i<n;i++){
        fprintf(fp,"%d\t",NUM[i]);
    }
    fprintf(fp,"\n");
    //Selection sort and recording the start time
    t3=clock();
    for(i=0;i<=n-2;i++){
        min=i;
        for(j=i+1;j<=n-1;j++){
            if(a[min]>a[j]){
                min=j;
            }
        }
        if(i!=min){
            t=a[i];
            a[i]=a[min];
            a[min]=t;
        }

    }
    t4=clock();//recording the end time
    fprintf(fp,"\nAfter sorting by Selection sort:\n");
    for(i=0;i<n;i++){
        fprintf(fp,"%d\t",a[i]);
    }
    fprintf(fp,"\n");
    //Insertion sort and recording the start time
    t5=clock();
    for(i=1;i<n;i++){
        value=b[i];
        int j=i;
        while(j>0&&b[j-1]>=value){
            b[j]=b[j-1];
            --j;
        }
        b[j]=value;
    }
    t6=clock();//recording the end time
    fprintf(fp,"\nAfter sorting by Insertion sort:\n");
    for(i=0;i<n;i++){
        fprintf(fp,"%d\t",b[i]);
    }
    fprintf(fp,"\n");

    cout<<"\n\nNo. of data\tBubble Sort\tSelection Sort\tInsertion Sort\n\n";
    cout<<n<<"\t\t"<<difftime(t2,t1)/CLOCKS_PER_SEC<<"\t\t"<<
    difftime(t4,t3)/CLOCKS_PER_SEC<<"\t\t"<<difftime(t6,t5)/CLOCKS_PER_SEC<<"\n\n";
    choose++;
    }//end of while
}//end of main
Output: ** Text file: lab_1

 2.Write a program that writes some numbers randomly in a file and then prompts user for an item to search using linear search both in iterative & recursive way and calculate the running time.
i) Iterative way

  

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<ctime>
#include<cstdio>
#include<cstdlib>
using namespace std;

int main()
{
    FILE *fp;
    fp = fopen("D:\\linearIterative.txt","w+");
    int N,i,key,r1,r2,count,test,choice;
    bool flag;
    double t1,t2;
    cout<<"\nHow many tests ?:> ";    // Prompt for no.of data test
    cin>>test;
    cout<<"\nRandom numbers ranging from _ to _:> ";  //Prompt for range of random numbers
    cin>>r1>>r2;
    choice = 1;
    while(choice<=test){
        cout<<"\nHow many data on test no."<<choice<<" :> ";

        cin>>N;
        int DATA[N];
        srand(time(0));
        fprintf(fp,"\nGenerated Random Numbers are on test - %d:\n\n",choice);
        //fprintf(fp,"\n\n");
        for(i=0;i<N;i++){
            DATA[i]=(r1+rand()%(r2-r1));
            fprintf(fp,"%d\t",DATA[i]);
        }
        fprintf(fp,"\n");
        cout<<"\nEnter the number which is to be searched:> ";
        cin>>key;
        t1 = clock();
        count = 0;
        flag = false;
        for(i=0;i<N;i++){
            count++;
            if(DATA[i]==key){
                flag = true;
                cout<<endl<<key<<" is found at the position "<<i+1<<"(position starts at 1)"<<endl;
                break;
            }
        }
        t2 = clock();
        if(flag==false){
            cout<<endl<<key<<" is not found in the list\n";
        }
        double time = difftime(t2,t1)/CLOCKS_PER_SEC;
        if(time==0){
            time = (double)(count*.000001);
        }
        cout<<"\nStep = "<<count<<endl;
        cout<<"\nNUM_of_DATA\tRequired Time\n\n";
        cout<<N<<"\t\t"<<time<<endl;
        choice++;
    }
}
Output text file: linearIterative.txt
II) Recursive way:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<ctime>
#include<cstdio>
#include<cstdlib>
using namespace std;

int N,i,key,r1,r2,count,test,choice,DATA[50000],ans;
bool flag;
double t1,t2;
int linearSearch(int num,int position)
{
    count++;
    if(num==DATA[position])
    {
        return position+1;
    }
    else
    {
        position++;
        return linearSearch(num,position);
    }

    return count;

}

int main()
{
    FILE *fp;
    fp = fopen("D:\\linearRecursive.txt","w+");

    cout<<"\nHow many tests ?:> ";    // Prompt for no.of data test
    cin>>test;
    cout<<"\nRandom numbers ranging from _ to _:> ";  //Prompt for range of random numbers
    cin>>r1>>r2;
    choice = 1;
    while(choice<=test){
        cout<<"\nHow many data on test no."<<choice<<" :> ";

        cin>>N;
        //int DATA[N];
        srand(time(0));
        fprintf(fp,"\nGenerated Random Numbers are on test - %d:\n\n",choice);
        for(i=0;i<N;i++){
            DATA[i]=(r1+rand()%(r2-r1));
            fprintf(fp,"%d\t",DATA[i]);
        }
        fprintf(fp,"\n");
        cout<<"\nEnter the number which is to be searched:> ";
        cin>>key;
        count = 0;
        t1=clock();
        ans=linearSearch(key,0);
        t2= clock();
        if(ans<=N){
            cout<<endl<<key<<" is found at the position "<<ans<<"(position starts at 1)"<<endl;
           // printf("Number %d found,position is %d ,Time complexity is %d",srch,ans,count);
        }
        else{
            cout<<endl<<key<<" is not found in the list\n";
        }
        double time = difftime(t2,t1)/CLOCKS_PER_SEC;
        if(time==0){
            time = (double)(count*.000001);
        }
        cout<<"\nStep = "<<count<<endl;
        cout<<"\nNUM_of_DATA\tRequired Time\n\n";
        cout<<N<<"\t\t"<<time<<endl;
        choice++;
    }
}
Output text file: linearrecursive.txt

3.Write a program that writes some numbers randomly in a file and then prompts user for an item to search using binary search both in iterative & recursive way and calculate the running time.

I) Iterative

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;

int main()
{
    FILE *fp;  // File declaration
    int n,r1,r2,choose,test,key,start,end,mid,flag,count;
    double t1,t2,t3,t4,t5,t6,tme;
    cout<<"\nHow many tests ? ";    // Prompt for no.of data test
    cin>>test;
    cout<<"\nRandom numbers ranging from _ to _ ";  //Prompt for range of random numbers
    cin>>r1>>r2;
    fp=fopen("D:\\binaryIterative.txt","w+");  //Opening file in 'D' Drive
    choose=1;
    while(choose<=test){
    cout<<"\nHow many numbers on test-"<<choose<<" :>";//Prompt for the no. of data in each test
    cin>>n;
    int NUM[n],a[n],b[n],i,p,t,j,value,min;
    srand(time(0));
    fprintf(fp,"\nGenerated Random Numbers are on test - %d:\n\n",choose);
    for(i=0;i<n;i++){
        NUM[i]=(r1+rand()%(r2-r1));
        fprintf(fp,"%d\t",NUM[i]);
    }
    for(i=0;i<n;i++){
        for(p=0;p<n-i;p++){
            if(NUM[p]>NUM[p+1]){
                t=NUM[p];
                NUM[p]=NUM[p+1];
                NUM[p+1]=t;
            }
        }
    }
    cout<<"\nEnter the number which is to be searched:> ";
    cin>>key;
    t1=clock();
    start=0;
    end=n-1;
    mid=(start+end)/2;
    count=0;
    while(start<=end){
        count++;
        if(NUM[mid]==key){
            flag=1;
            break;
        }
        if(key>NUM[mid]){
            start=mid+1;
        }
        else{
            end=mid-1;
        }
        mid=(start+end)/2;
    }
    t2=clock();
    tme=difftime(t2,t1)/CLOCKS_PER_SEC;
    if(flag==1){
        printf("\nNumber %d found at position %d, \n",key,mid+1);
    }
    else if(flag==0){
        printf("\nDid not find the number (%d)\n",key);
    }
    if(tme==0){
        tme=(double)(count*.000001);
    }
    cout<<"\nRunning time = "<<tme<<endl;
    choose++;

}
}
Output text file: binaryIterative.txt


 II) Recursive

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;

int N,i,key,r1,r2,test,choice,DATA[50000],ans,p,t;
int start,en_d,mid;
bool flag;
double t1,t2,tme;
int count = 0;
int binarySearch(int a[],int value,int start,int en_d)
{
    count++;
    if(en_d<start){
        flag = false;
        return -1;
    }
    mid = (en_d + start)/2;
    if(a[mid]>value){
        return binarySearch(a,value,start,mid-1);
    }
    else if(a[mid]<value){
        return binarySearch(a,value,mid+1,en_d);
    }
    else{
        flag = true;
        return mid;
    }

}
int main()
{
    FILE *fp;

    fp = fopen("D:\\binaryRecursive.txt","w+");

    cout<<"\nHow many tests ?:> ";    // Prompt for no.of data test
    cin>>test;
    cout<<"\nRandom numbers ranging from _ to _:> ";  //Prompt for range of random numbers
    cin>>r1>>r2;
    choice = 1;
    while(choice<=test){
        cout<<"\nHow many data on test no."<<choice<<" :> ";

        cin>>N;
        //int DATA[N];
        srand(time(0));
        fprintf(fp,"\nGenerated Random Numbers are on test - %d:\n\n",choice);
        for(i=0;i<N;i++){
            DATA[i]=(r1+rand()%(r2-r1));
            fprintf(fp,"%d\t",DATA[i]);
        }
        fprintf(fp,"\n");
        for(i=0;i<N;i++){
            for(p=0;p<N-i;p++){
                if(DATA[p]>DATA[p+1]){
                    t=DATA[p];
                    DATA[p]=DATA[p+1];
                    DATA[p+1]=t;
                }
            }
        }
        cout<<"\nEnter the number which is to be searched:> ";
        cin>>key;
        t1=clock();
        start=0;
        en_d=N-1;
        //mid=(start+end)/2;
        binarySearch(DATA,key,start,en_d);
        t2=clock();
        tme=difftime(t2,t1)/CLOCKS_PER_SEC;

        if(flag==true){
            printf("Number %d found at position %d, \n",key,mid+1);
        }
        else if(flag==false){
            printf("\nDid not find the number (%d)\n",key);
        }
        if(tme==0){
            tme=(double)(count*.000001);
        }
        cout<<"\nRunning time = "<<tme<<endl;
        choice++;

    }
}
Output text file: BinaryRecursive

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

এতে সদস্যতা: মন্তব্যসমূহ (Atom)