Need help with program. It\'s supposed to Run experiments varying n (where n is

Question

Need help with program. It's supposed to Run experiments varying n (where n is the number of elements) from 5000 to 100000, with increment 5000. For each n value, run each algorithm 10 times on different input arrays and take the average of the running times. To generate numbers, use a random number generator. Then for each array instance run the algorithms.

But instead is running same input array each time. Here's code in c++. what should I change to fix

#include <cstdlib>

#include <iostream>

#include <vector>

#include <ctime>

#include <chrono>

#define RAND_MAX = 4000;

using namespace std;

//functions prototype

vector<int> insertionSort(vector<int> v, int n);

//function defintion

vector<int> insertionSort(vector<int> v, int n)

{

int key, i;

for (int j = 1; j < v.size(); 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;

}

//main function

int main()

{

//declare variables

int n, t1, t2, t_alg1, t_avg, p = 0, r = 0, q, i, j;

double totaltime, avg;

vector<double> time;

using std::chrono::system_clock;

vector<int> a;

vector<vector<int>> v;

vector<vector<int>> b;

v.resize(10);

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

v[i].resize(100000);

}

for (int i = 0; i < 10; i++)

{ //each algorithm is run 10x

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

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

//RRowxCcolumns

v[i][j] = rand();

}

}

//measurements for insertion sort

cout << "insertion sort algorithm " << endl << "*****************************************************" << endl;

for (int n = 5000; n <= 100000; n = n + 5000) {//run n times from 5000 -100000 with increment

totaltime = 0;

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

//measurements for insertion sort

auto t1 = std::chrono::high_resolution_clock::now();

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

//a.clear();

insertionSort(a,n);

//mergeSort(a, p,r);

auto t2 = std::chrono::high_resolution_clock::now();

auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();

time.push_back(duration);

a.clear();

}

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

totaltime += time[i];

cout <<"i:" <<i<<' '<<"n:"<<n << ' ' << time[i] << endl;

avg = totaltime / 10;

}

cout << "average time: " << avg << "ms" << endl << endl;

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

}

return 0;

}

Explanation / Answer

The problem is with the rand() function. rand() is a psuedo random generator. It generates the same sequence of numbers, when they are called again. So to generate random like numbers we use the srand() function. Which takes the seed value as argument. When seed value is set to a different value using srand() rand() generates a different random number. Simply srand() must be intiated with run time continuosly varying variable. Generally as a standard time function is used to pass as seed value.

so before using rand()

place a statement srand(time(NULL)); now each time rand() is called you will get a different number and your problem is solved.

time() function uses the header ctime so please include that.

and time() returns the number of seconds from epoch time. which is changing and unique for every second and thus makes a run time changing variable.

/* hope this helps */

/* if any queries please comment */

/* thank you */

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

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