Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //terina burr
- //section one
- //assign two
- //due 10/11/15
- #include <iostream>
- #include <vector>
- #include <cstdlib>
- #include <algorithm>
- #include <iomanip>
- using namespace std;
- const int TOBE_SEARCHED = 5000;
- const int HIGH = 10000;
- const int LOW = 1;
- void genRndNums( vector<int>& v, int vec_size, int seed );
- bool linearSearch( const vector<int>& v, int x) ;
- bool binarySearch( const vector<int>& v, int x) ;
- int search( const vector<int>& container, const vector<int>& searchNums,
- bool (*p)( const vector<int>&, int) ) ;
- void sortVec (vector<int>& v) ;
- void printStat (int totalSucCnt, int vec_size);
- int main() {
- vector<int> container, tobeSearched;
- genRndNums(container, 10000, 9);
- genRndNums(tobeSearched, TOBE_SEARCHED, 3);
- cout << "\nConducting linear search ..." << endl;
- int linear_search_count = search( container, tobeSearched, linearSearch );
- printStat ( linear_search_count, TOBE_SEARCHED );
- cout << "\nConducting binary search on unsorted container ..." << endl;
- int binary_search_count = search( container, tobeSearched, binarySearch );
- printStat ( binary_search_count, TOBE_SEARCHED );
- sortVec( container );
- cout << "\nConducting binary search on sorted container ..." << endl;
- binary_search_count = search( container, tobeSearched, binarySearch );
- printStat ( binary_search_count, TOBE_SEARCHED );
- return 0;
- }
- /***************************************************************
- Function: genRndNums
- Use: it generates random number
- Arguments: 1. V: the vector that it puts the random numbers in
- 2. vec_size: the size of the vector you want to have
- 3. seed:
- Returns: nothing
- ***************************************************************/
- void genRndNums( vector<int>& v, int vec_size, int seed ) {
- srand(seed);
- int x;
- for(int i = 0; i<vec_size; i++)
- //this loop goes through a vector and inserts the random numbers
- {
- x = rand() % HIGH + LOW;
- v.push_back(x);
- }
- }
- /***************************************************************
- Function: linearSearch
- Use: it starts searching for x at the beginning of the vector v
- Arguments: 1. V: the vector that it searches
- 2. x: is the item that it searches
- Returns: true or false whether the item x is in the vector v or not returns true if the item x is in the vector v returns false if the item x is not in the vector v
- ***************************************************************/
- bool linearSearch( const vector<int>& v, int x) {
- if(std::find(v.begin(), v.end(), x) !=v. end())
- {
- //if they find the correct value and it is not equal to the last one it returns true
- return true;
- }
- else
- return false;
- //otherwise it returns false
- }
- /***************************************************************
- Function: binarySearch
- Use: it uses the algorithm binary search to find the value x in the array v
- Arguments: 1. V: the vector that it searches
- 2. x: is the item that it searches
- Returns: true or false whether the item x is in the vector v or not returns true if the item x is in the vector v returns false if the item x is not in the vector v
- ***************************************************************/
- bool binarySearch( const vector<int>& v, int x) {
- if ( binary_search( v.begin(), v.end(), x ) )
- return true;
- //if they find the correct value return true
- else
- return false;
- //else return false
- }
- /***************************************************************
- Function: search
- Use: it is used to compute the total number of successful searches
- Arguments: 1. container: the vector that it searches from
- 2. searchNums: the numbers its suppose to search
- 3. p: a pointer to a search routine
- Returns: the total number of successful searches
- ***************************************************************/
- int search( const vector<int>& container, const vector<int>& searchNums,
- bool (*p)( const vector<int>&, int) ) {
- int x = 0;
- for(unsigned int i = 0; i<searchNums.size(); i++)
- {
- //goes through the second vector and stops when it reaches its size
- if(p(container,searchNums.at(i))==true)
- {
- //it points to a search function and if that search function goes through as true then it adds one to the total it says going through vector one
- x++;
- }
- }
- return x;
- }
- /***************************************************************
- Function: sortVec
- Use: it is used to sort a vector from smallest to largest using the algorithm sort
- Arguments: 1. v: the vector that it is going to sort
- Returns: nothing
- ***************************************************************/
- void sortVec (vector<int>& v) {
- //sorts a vector from smallest to largest
- sort(v.begin(), v.end() );
- }
- /***************************************************************
- Function: printStat
- Use: it is used to print out the percentage of successful searches
- Arguments: 1. totalSucCnt: total number of successful searches
- 2. vec_size: the size of the vector
- Returns: nothing
- ***************************************************************/
- void printStat (int totalSucCnt, int vec_size) {
- float x =( float(totalSucCnt)/vec_size)*100;
- //gives the percentage number of successes as a float
- std::cout.width(6); std::cout << std::right <<"Percent of successful searches = "<<setw(4)<< x<<"%"<<'\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement