C++ Program For this computer assignment, you are to write and implement a C++ p

Question

C++ Program

For this computer assignment, you are to write and implement a C++ program to implement two search algorithms ( a linear search and a binary search) on randomly generated integers stored in vectors.

• void Vectors ( vector < int >& v1, vector < int >& v2, int s1, int s2 ): Fills the elements of vectors v1 of size ARR_SIZE = 200 and v2 of size TEST_ARR_SIZE = 100 with random numbers, generated by two sets of pseudo-random numbers with the seed values s1 and s2, where s1 (defined as SEED1 = 1) is for v1and s2 (defined as SEED2 = 3) is for v2. To initiate a random number generator (RNG) with the seed value seed, execute the system function srand ( seed ) (only once), and to generate a random integer in the range [ LOW = 1, HIGH = 1000 ], execute: rand ( ) % ( HIGH – LOW + 1 ) + LOW.

• bool linearSearch ( const vector < int >& v, int x ): A linear search algorithm, where x is the searched item in vector v. It simply starts searching for x from the beginning of vector v to the end, but it stops searching when there is a match. If the search is successful, it returns true; otherwise, it returns false. To implement this routine, simply call the find ( ) function in the STL. • bool binarySearch ( const vector < int >& v, int x ): A binary search algorithm, where x is the searched item in vector v. If the search is successful, it returns true; otherwise, it returns false. To implement this routine, simply call the binary_search ( ) function in the STL.

• int search ( const vector < int >& v1, const vector < int >& v2, bool (*p ) ( const vector < int >&, int ) ): A generic search algorithm – takes a pointer to the search routine p ( ), and then it calls p ( ) for each element of vector v2 in vector v1. It computes the total number of successful searches and returns that value to the main ( ) routine as an input argument to the print routine printStat ( ), which is used to print out the final statistics for a search algorithm.

• void sortVector ( vector < int >& v ): A sort algorithm to sort the elements of vector v in ascending order. To implement this routine, simply call the sort ( ) function in the STL. Search Algorithms 2

• void printVector ( const vector < int >& v ): Prints the contents of vector v on stdout, up to NO_ITEMS = 16 items on a single line except perhaps the last line. The sorted numbers need to be properly aligned on the output. For each printed number, allocate ITEM_W = 4 spaces for each item.

• void printStat ( int totalSucCnt, int vectorSz ): Prints the percent of successful searches as right-aligned, floating-point numbers on stdout, where totalSucCnt is the total number of successful comparisons and vectorSz is the size of the test vector.

Explanation / Answer

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <iomanip>
using namespace std;

const int LOW = 1;
const int HIGH = 100;
const int SEED = 345;
const int NO_ITEMS = 10;
const int ITEM_W = 6;

void genRndNums ( vector < int >& v, int seed );
bool linearSearch ( const vector < int >& inputVec, int x );
bool binarySearch ( const vector < int >& inputVec, int x );
int search ( const vector < int >& inputVec, const vector < int >& searchVec, bool ( *p ) ( const vector<int>&, int ) );
void sortVector ( vector < int >& inputVec );
void printStat ( int totalSucCnt, int vec_size );
void print_vec ( const vector < int >& vec );

int main()
{
vector<int> numbers(NO_ITEMS);
vector<int> searchNums(NO_ITEMS);
int successCnt;

cout << "Generating random numbers" << endl;
genRndNums(numbers, SEED); //generate some random numbers
print_vec(numbers);

cout << "Generating random search numbers" << endl;
genRndNums(searchNums, 123); //generate some random numbers to be searched
print_vec(searchNums);

cout << "Sorting numbers" << endl;
sortVector(numbers);

cout << "Performing linear search" << endl;
successCnt = search(numbers, searchNums, linearSearch); //find the success count for linear search
printStat(successCnt, searchNums.size());

cout << "Performing binary search" << endl;
successCnt = search(numbers, searchNums, binarySearch); //find the success count for linear search
printStat(successCnt, searchNums.size());

}

void genRndNums ( vector < int >& v, int seed )
{
srand(seed);
for(int i = 0; i < v.size(); i++)
v[i] = (rand ( ) % ( HIGH - LOW + 1 ) + LOW);
}

bool linearSearch ( const vector < int >& inputVec, int x )
{
for(int i =0 ; i< inputVec.size(); i++)
{
if(inputVec[i] == x)
return true;
}

return false;
}
bool binarySearch ( const vector < int >& inputVec, int x )
{
int start = 0;
int end = inputVec.size() - 1;
int mid;
while(start <= end)
{
mid = (start + end) / 2;
if(inputVec[mid] == x)
return true;
else if(inputVec[mid] < x)
start = mid + 1;
else
end = mid - 1;
}

return false;
}

int search ( const vector < int >& inputVec, const vector < int >& searchVec, bool (*p)(const vector <int >&, int))
{
int success = 0;
for(int i = 0; i < searchVec.size(); i++)
{
if(p(inputVec, searchVec[i]))
success++;
}
return success;
}
void sortVector ( vector < int >& inputVec )
{
sort(inputVec.begin(), inputVec.end());
}
void printStat ( int totalSucCnt, int vec_size )
{
double percent = totalSucCnt * 100.0 / vec_size;
cout << fixed << setprecision(2) << "Successful searches: " << percent << "%" << endl;
}
void print_vec ( const vector < int >& vec )
{
for(int i = 0; i < vec.size(); i++)
{
if(i % NO_ITEMS == 0)
cout << endl;

cout << setw(ITEM_W) << vec[i];
}
cout << endl;
}

output
======
Generating random numbers

16 91 66 85 50 16 29 13 38 72
Generating random search numbers

62 76 56 3 36 35 78 94 29 50
Sorting numbers
Performing linear search
Successful searches: 20.00%
Performing binary search
Successful searches: 20.00%

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.