#include <cstdlib> #include <iostream> #include <vector> #include <ctime> #defin

Question

#include <cstdlib>
#include <iostream>
#include <vector>
#include <ctime>
#define RAND_MAX = 40000;
using namespace std;
//functions
vector<int> insertionSort(vector<int> v);
vector<int> vector_get(int n)
{
int i;
int d;
vector<int> v;

srand(time(nullptr)); //initialse the random number generator
for (i = 0; i < n; ++i)
{
v.push_back(rand()%40000); //to generate random number between 0 and 40000 and put it in vector
}
return v;
}
//prints a vector
void vector_print(vector<int> v)
{
size_t i;
for (i = 0; i < v.size() - 1; ++i)
{
cout << v[i] << ", ";
}
cout << v[i] << endl;
}

vector<int> insertionSort(vector<int> v)
{
int key,i;
for (int j = 1; j <= v.size()-1; j++)
{

key = v[j];
i = j - 1;
while (i >= 0 && v[i] > key){
v[i + 1] = v[i];
i = i - 1;
}
v[i + 1] = key;

}
return v;
}
int main()
{
//declare variables
int n,t1,t2, t_alg1,t_avg;
vector<int> a;

vector<int> v;

vector<int> b;

//ask user how many values they want to enter
cout << "Please enter how many values would you like to enter?: ";
cin >> n;
//get elements for vector a
a = vector_get(n);
//print vector a
cout << "unsorted: ";
vector_print(a);
//print sorted vector a
cout << "sorted: ";

//as insertionSort(vector<int> v) returns a vector<int> we can use it anywhere a vector<int> is expected, such as as the argument for vector_print
vector_print(insertionSort(a));

//generate numbers for v[1...10,1...100000]

for(int i=1; i<=10;i++){

for(int j=1; j<=100000;j++){

v[i,j]=rand();

}

}

//measurements for insertion sort

for(int n=5000;n<=100000;n=n+5){

for(int i=1;i<=10;i++){

//create a copy array so can use for multiple calculations

b[n]=v[i,n];

t1=time();

//in psuedocode: (alg1=insertion sort) says alg1(v,n) here

t2=time();

t_alg1[i,n]=t2-t1;

//compute average says (t_avg-t_avg=t_alg1[1,n]+t_alg1[2,n]+...+t_alg1[10,n])/10

}

}
//main returns 0 upon successful completion
return 0;
}

Explanation / Answer

Here is the update for you.

To get the system time just use the method

time(NULL) which is part of the ctime header in C++

If you're using java you can call timeInMilliSeconds() method.

So, to get the time before sorting the step is:

t1 = time(NULL);

And after sorting again:

t2 = time(NULL);

Now the difference is: t2 - t1 will give the time taken to run the algorithm.

#include <cstdlib>
#include <iostream>
#include <vector>
#include <ctime>
#define MY_RAND_MAX 40000
using namespace std;
//functions
vector<int> insertionSort(vector<int> v);
vector<int> vector_get(int n)
{
int i;
int d;
vector<int> v;
srand(time(nullptr)); //initialse the random number generator
for (i = 0; i < n; ++i)
{
v.push_back(rand() % MY_RAND_MAX); //to generate random number between 0 and 40000 and put it in vector
}
return v;
}
//prints a vector
void vector_print(vector<int> v)
{
size_t i;
for (i = 0; i < v.size() - 1; ++i)
{
cout << v[i] << ", ";
}
cout << v[i] << endl;
}

vector<int> insertionSort(vector<int> v)
{
int key,i;
for (int j = 1; j <= v.size()-1; j++)
{

key = v[j];
i = j - 1;
while (i >= 0 && v[i] > key){
v[i + 1] = v[i];
i = i - 1;
}
v[i + 1] = key;

}
return v;
}
int main()
{
//declare variables
int n,t1,t2, t_alg1,t_avg;
vector<int> a;
vector<int> v;
vector<int> b;
//ask user how many values they want to enter
cout << "Please enter how many values would you like to enter?: ";
cin >> n;
//get elements for vector a
a = vector_get(n);
//print vector a
cout << "unsorted: ";
vector_print(a);
//print sorted vector a
cout << "sorted: ";

//as insertionSort(vector<int> v) returns a vector<int> we can use it anywhere a vector<int> is expected, such as as the argument for vector_print
vector_print(insertionSort(a));
//generate numbers for v[1...10,1...100000]
int k = 0;
for(int i=1; i<=10;i++){
for(int j=1; j<=100000;j++){
v[k++]=rand();
}
}
//measurements for insertion sort
k = 0;
for(int n=5000;n<=100000;n=n+5){
for(int i=1;i<=10;i++){
//create a copy array so can use for multiple calculations
b[n]=v[k];
t1=time(NULL);
//in psuedocode: (alg1=insertion sort) says alg1(v,n) here
t2=time(NULL);
t_alg1 += t2-t1;
//compute average says (t_avg-t_avg=t_alg1[1,n]+t_alg1[2,n]+...+t_alg1[10,n])/10

}
}
//main returns 0 upon successful completion
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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