Question

C++ on randomly generated integers stored in vectors. you will use routines from STL <algorithm> to implement these algorithms. Using the following functions with their description

const int DATA_SIZE = 200;

const int SEARCH_SIZE = 100;

const int DATA_SEED = 7;

const int SEARCH_SEED = 9;

void genRndNums( vector<int>& v, int seed )

{

This routine generates random integers in the range [ LOW = 1, HIGH =200 ] and puts them in vector v. Initializes the random number generator (RNG) by calling the function srand ( ) with the seed value seed, and generates random integers by calling the function rand ()^{. To use} srand ^and rand, you need the header <cstdlib>. The vector v is already allocated with space. Use vector’s member function to get the size of the vector

}

int linearSearch( const vector<int>& inputVec, int x)

{

int linearSearch ( const vector < int >& inputVec, int x ) : A linear search algorithm, where x is the searched item in vector inputVec. 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 the position (starting at 0) of found item; otherwise, it returns -1. To implement this routine, simply call the find ( ) function from the STL <algorithm>.

}

int binarySearch( const vector<int>& inputVec, int x)

{

A binary search algorithm, where x is the searched item in vector inputVec. If the search is successful, it returns the position (starting at 0) of found item; otherwise, it returns -1. To implement this routine, simply call the equal_range ( ) function from the STL <algorithm>.

}

int search( const vector<int>& inputVec, const vector<int>& searchVec,

            int (*p)( const vector<int>&, int) )

{

int search ( const vector < int >& inputVec, const vector < int >& searchVec, int ( *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 searchVec ^{in vector} inputVec. 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>& inputVec)

{

A sort algorithm to sort the elements of vector inputVec in ascending order. To implement this routine, simply call the sort ( ) function from the STL.

}

void printStat (int totalSucCnt, int vec_size)

{

the percent of successful searches as floating-point numbers on stdout, where totalSucCnt is the total number of successful comparisons and vec_size is the size of the test vector

}

void print_vec( const vector<int>& vec )

{

This routine displays the contents of vector vec on standard output, printing exactly NO_ITEMS = 12 numbers 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 = 5 spaces on standard output. You can re-use the implementation of this routine from Assignment 1, but remember to change the values of related constants.

  

}

int main() {

    vector<int> inputVec(DATA_SIZE);

    vector<int> searchVec(SEARCH_SIZE);

    genRndNums(inputVec, DATA_SEED);

    genRndNums(searchVec, SEARCH_SEED);

    cout << "----- Data source: " << inputVec.size() << " randomly generated numbers ------" << endl;

    print_vec( inputVec );

    cout << "----- " << searchVec.size() << " random numbers to be searched -------" << endl;

    print_vec( searchVec );

    cout << "\nConducting linear search on unsorted data source ..." << endl;

    int linear_search_count = search( inputVec, searchVec, linearSearch );

    printStat ( linear_search_count, SEARCH_SIZE );

    cout << "\nConducting binary search on unsorted data source ..." << endl;

    int binary_search_count = search( inputVec, searchVec, binarySearch );

    printStat ( binary_search_count, SEARCH_SIZE );

    sortVector( inputVec );

    cout << "\nConducting linear search on sorted data source ..." << endl;

    linear_search_count = search( inputVec, searchVec, linearSearch );

    printStat ( linear_search_count, SEARCH_SIZE );

    cout << "\nConducting binary search on sorted data source ..." << endl;

    binary_search_count = search( inputVec, searchVec, binarySearch );

    printStat ( binary_search_count, SEARCH_SIZE );

    return 0;

}

Answer 1

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <iomanip>

using namespace std;

const int DATA_SIZE = 200;
const int SEARCH_SIZE = 100;
const int DATA_SEED = 7;
const int SEARCH_SEED = 9;

int getRandomNumberInRange(int min, int max)
{
return rand()%(max - min + 1) + min;
}

void genRndNums( vector<int>& v, int seed )
{
int LOW = 1;
int HIGH = 200;
srand(seed);

for(int i = 0; i < v.size(); i++)
{
v[i] = getRandomNumberInRange(LOW, HIGH);
}
}

int linearSearch( const vector<int>& inputVec, int x)
{
vector<int>::const_iterator p = find(inputVec.begin(), inputVec.end(), x);
if (p == inputVec.end())
{
return -1;
}
else
{
return p - inputVec.begin();
}
}

int binarySearch( const vector<int>& inputVec, int x)
{
pair<vector<int>::const_iterator,vector<int>::const_iterator> bounds;
bounds = equal_range(inputVec.begin(), inputVec.end(), x);
if (bounds.first == inputVec.end())
{
return -1;
}
else
{
return (bounds.first - inputVec.begin());
}
}

int search( const vector<int>& inputVec, const vector<int>& searchVec,
int (*p)( const vector<int>&, int) )
{
int search = 0;
  
for(int i = 0; i < searchVec.size(); i++)
{
if (p(inputVec, searchVec[i]) != -1)
{
search++;
}
}
return search;
}

void sortVector (vector<int>& inputVec)
{
sort(inputVec.begin(), inputVec.end());
}

void printStat (int totalSucCnt, int vec_size)
{
double successPercent = (double)(totalSucCnt)/vec_size;
cout << "percent of successful searches: " << cout << fixed << setprecision(2) << successPercent << " %" <<endl;
}

void print_vec( const vector<int>& vec )
{
int NO_ITEMS = 12;

for(int i = 0; i < vec.size(); i++)
{
cout.width(5) << vec[i];
if (((i+1) % NO_ITEMS) == 0)
{
cout << endl;
}
}
}

int main() {
vector<int> inputVec(DATA_SIZE);
vector<int> searchVec(SEARCH_SIZE);
genRndNums(inputVec, DATA_SEED);
genRndNums(searchVec, SEARCH_SEED);

cout << "----- Data source: " << inputVec.size() << " randomly generated numbers ------" << endl;
print_vec( inputVec );
cout << "----- " << searchVec.size() << " random numbers to be searched -------" << endl;
print_vec( searchVec );

cout << "\nConducting linear search on unsorted data source ..." << endl;
int linear_search_count = search( inputVec, searchVec, linearSearch );
printStat ( linear_search_count, SEARCH_SIZE );

cout << "\nConducting binary search on unsorted data source ..." << endl;
int binary_search_count = search( inputVec, searchVec, binarySearch );
printStat ( binary_search_count, SEARCH_SIZE );

sortVector( inputVec );

cout << "\nConducting linear search on sorted data source ..." << endl;
linear_search_count = search( inputVec, searchVec, linearSearch );
printStat ( linear_search_count, SEARCH_SIZE );

cout << "\nConducting binary search on sorted data source ..." << endl;
binary_search_count = search( inputVec, searchVec, binarySearch );
printStat ( binary_search_count, SEARCH_SIZE );

return 0;
}