Question

C++ please read all the question

Create 3 large arrays to search, where the size will be variable up until it reaches your machines limit.

They should contain the same information since we are going to compare 3 different algorithms.You are going to do operational studies on them to determine their order.
O(N), O(log(N)), and O(1)?
Search algorithms.Linear, Binary, Hash
You should know which algorithms are what order,now you are going to prove it.
Fill the 3 arrays with the same information but use random strings of say size 20 characters.Or use 1 array and 3 separate programs.
You will perform searches on the arrays given strings that are in the array and those that are not. Make this about a 50-50 mix, or at least know what the mix is.
a) Perform the linear search, record the time. If it does it very quickly you will need to adjust the size and the number of loops over the data till you get a few seconds. Then start increasing N. The object is to see how time increases as N increases.
b) Perform the same task with the Binary Search.Obviously using Binary the data first has to be ordered. This is an O(N^2) to O(NlogN) function just on it's own but it only needs to be done once. Don't take this time into account. Yes, I know that's bad, but I just want to show specific algorithm differences not including the sort.
c) Perform the same task with the Hash function.This is tricky since you have to develop the Hash function. Also, I want you to use chaining. This makes it easy since there are no collisions and you don't have to use algorithms for collisions, just use a linked list when a collision occurs.
When done, plot the results of each algorithm as Time vs. N It should be easy to conclude the order of the algorithm.

Answer 1

CODE:

#include<iostream>

#include <stdio.h>

#include <unistd.h>

#include <stdlib.h>

#include<time.h>

#include <list>

using namespace std;

class Algorithms

{

public:

int *LinearArray;

int *BinaryArray;

int *Temp_array;

int size,count;

list<int> *table;

int BUCKET;

public:

Algorithms(int size)

{

LinearArray = (int *)malloc(20 * sizeof(int));

BinaryArray = (int *)malloc(20 * sizeof(int));

Temp_array = (int *)malloc(20 * sizeof(int));

this->size=size;

this->BUCKET=size;

table=new list<int>[BUCKET];

}

~Algorithms()

{

delete LinearArray;

delete BinaryArray;

delete Temp_array;

}

public:

void readData()

{

int random_Number;

srand((unsigned)time(0));

for(int i=0;i<size;i++)

{

random_Number=(rand()%100)+1;

Temp_array[i]=BinaryArray[i]=LinearArray[i]=random_Number;

}

}

public:   

void printdata()

{

for(int i=0;i<size;i++)

{

cout<<Temp_array[i]<<"\t";

}

cout<<"\n"<<endl;

}

public:

void Linear_Search(int key)

{

bool status=false;

int i;

for(i=0;i<size;i++)

{

if(key==LinearArray[i])

{

status=true;

break;

}

}

if(status==false)

cout<<"\nThe Key is Not Found"<<endl;

else

cout<<"\nThe Key is present at "<<i <<" Location"<<endl;

}

public:

int binarySearch(int array[], int leftindex, int rightindex, int key)

{

if (rightindex>= leftindex)

{

int mid =leftindex+ (rightindex -leftindex)/2;

if (array[mid] == key)  

return mid;

if (array[mid] > key)

return binarySearch(array,leftindex, mid-1,key);

return binarySearch(array, mid+1,rightindex,key);

}

return -1;

}

void insertItem(int key)

{

int index = hashFunction(key);

table[index].push_back(key);

}

int hashFunction(int x)

{

return (x % BUCKET);

}

int HashSearch(int key)

{

list <int> :: iterator i;

int index = hashFunction(key);

for (i = table[index].begin();i != table[index].end(); i++)

{

if (*i == key)

return 0;

}

return -1;

}

};

int main()

{

Algorithms obj(10);

time_t start,end;

double tc;

cout<<"\n------------------------------"<<endl;

cout<<"\n*** Implementation Of the Algorithm ***"<<endl;

obj.readData();

cout<<"\nInput Data Elements are"<<endl;

obj.printdata();

cout<<"\nEnter the key to Search in a list"<<endl;

int key;

cin>>key;

cout<<"\nPerforming Linear search "<<endl;

start=clock();

obj.Linear_Search(key);

end=clock();

tc=(difftime(end,start)/CLOCKS_PER_SEC);

cout<<"\ntime efficiency of Linear search is: "<<tc<<endl;

start=clock();

cout<<"\nNow Performing Binary Search "<<endl;

int result=obj.binarySearch(obj.BinaryArray,0,obj.size,key);

if(result==-1)

{

cout<<"\nThe Key is Not found Binary Search "<<endl;

}

else

cout<<"\nThe Key is Found at "<<result<<" Location"<<endl;

end=clock();

tc=(difftime(end,start)/CLOCKS_PER_SEC);

cout<<"\ntime efficiency of Binary search is: "<<tc<<endl;

for(int i=0;i<obj.size;i++)

{

obj.insertItem(obj.Temp_array[i]);

}

cout<<"\nNow Performing Hash Function "<<endl;

result=obj.HashSearch(key);

if(result==-1)

cout<<"\nKey Not Found in Hashtable"<<endl;

else

cout<<"\nKey is Found in Hashtable"<<endl;

}

Sample Output:-

--------------------

------------------------------

Implementation Of the Algorithm

Input Data Elements are

35 94 79 59 60 28 57 47 15 36

Enter the key to Search in a list

15

Performing Linear search

The Key is present at 8 Location

time efficiency of Linear search is: 0

Now Performing Binary Search

The Key is Not found Binary Search

time efficiency of Binary search is: 0

Now Performing Hash Function

Key is Found in Hashtable

--------------------------------

Process exited after 52.19 seconds with return value 0

Press any key to continue . . .

Implementation Of the Algorithm** Input Data Elements are 59 28 57 35 94 79 60 47 15 36 Enter the key to Search in a list 15 Performing Linear search The Key is present at 8 Location time efficiency of Linear search is: e Now Performing Binary Search The Key is Not found Binary Search time efficiency of Binary search is: e Now Performing Hash Function Key is Found in Hashtable Process exited after 52.19 seconds with return value e Press any key to continue . . .

Please like it........