a. Here is pseudocode for a program that inputs a value n from the user and then inserts n random numbers, ensuring that there are no duplicates:
Input n from user Create vector v of type int
Loop i = 1 to n
r = random integer between 0 and n-1
Linearly search through v for value r
if r is not in vector v then add r to the end of v
End Loop
Print out number of elements added to v
Implement this program with your own linear search routine and add wrapper code that will time how long it takes to run. Test the program for different values of n . Depending on the speed of your system, you may need to input large values for n so that the program takes at least one second to run. Here is a sample that indicates how to calculate the difference in time: (time.h is a library that should be available on your version of C++).
#include <time.h>
time_t start,end;
double dif;
time (&start); // Record start time
// Rest of program goes here.
time (&end); // Record end time
dif = difftime(end,start);
cout << "It took " << dif << " seconds to execute. " << endl;
b. Next, create a second program that has the same behavior except that it uses an STL set to store the numbers instead of a vector:
Input n from user
Create set s of type int
Loop i = 1 to n
r = random integer between 0 to n-1
Use s.find(r) to search if r is already in the set
if r is not in set s then add r to s
End Loop
Print out number of elements added to s
Time your new program with the same values of n that you used in the vector version. What do the results tell you about the Big- O run time of the find( ) function for the set compared with linear search through the vector? Note that the find( ) function is really redundant because insert has no effect if the element is already in the set. However, use the find( ) function anyway to create a program comparable to the vector algorithm.
part a.
#include <iostream>
#include <vector>
#include <time.h>
#include <algorithm>
int n, r;
time_t start, end;
double dif;
int main()
{
std::cin >> n;
time(&start);
std::vector<int> v;
srand(time(NULL));
for (int i = 1; i <= n; i++)
{
r = rand() % (n - 1) + 0;
std::vector<int>::const_iterator it = std::find(v.begin(), v.end(), r);
if (std::find(v.begin(), v.end(), r) != v.end())
{
it == v.end();
}
else
{
v.push_back(r);
}
}
std::cout << std::endl << "There are " << int(v.size()) << " numbers stored in this vector." << std::endl;
time(&end);
dif = difftime(end, start);
std::cout << "It took about " << dif << " second(s) to finish the program. " << std::endl << std::endl;
system("pause");
return 0;
}