/
linear_search.cpp
78 lines (64 loc) · 2.19 KB
/
linear_search.cpp
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
#include<iostream>
#include<ctime> //for time
#include<stdlib.h> //random ()
#include<fstream> //for file
using namespace std;
int main()
{ int best, avg, worst;
best=avg=worst=0;
ofstream f("graph.txt");
ofstream f1("graph_best.txt"); //store number of best cases in linear search
ofstream f2("graph_avg.txt"); //store number of average cases in linear search
ofstream f3("graph_worst.txt"); //store number of worst cases in linear search
int size_array=50;
double sum_array=0;
int num_case=10000;
while(size_array<=5000) //Loop till array size reaches 5000
{
for(int z=0;z<num_case;z++) // Run for 10,000 cases
{
int a[size_array];
int key=rand(); //random key selected
for(int i=0;i<size_array;i++) // To enter random values in array
{
a[i]=rand();
}
clock_t start, endi;
start=clock();
int flag=0; // if key is not found, then flag = 0 else flag = 1
for(int k=0;k<size_array;k++) //To search key in array
{
if(a[k]==key)
{ flag=1;
if(k<=0.25*size_array)
{
best++;
}
if(k<=0.75*size_array && k>0.25*size_array)
{
avg++;
}
if(k>0.75*size_array)
{
worst++;
}
break;
}
}
if(flag==0)
worst++;
endi=clock();
double duration=endi-start/(double) CLOCKS_PER_SEC; //converting time unit to second
sum_array+=duration;
}
cout<<"size: "<<size_array<<'\t'<<"Time: "<<sum_array/100000<<'\t'<<'\t'<<"best: "<<best<<'\t'<<"avg: "<<avg<<'\t'<<"worst: "<<worst<<endl;
//storing values in file
f<<size_array<<'\t'<<sum_array/100000<<endl;
f1<<size_array<<'\t'<<best<<endl;
f2<<size_array<<'\t'<<avg<<endl;
f3<<size_array<<'\t'<<worst<<endl;
size_array+=50;
sum_array=best=avg=worst=0;
}
return 0;
}