Help!!! My code gives same values when n is 10000,15000...100000 as it does when

Question

Help!!! My code gives same values when n is 10000,15000...100000 as it does when n=5000. It should give different numbers and averages should be different.

Instruction says 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.

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

#define RAND_MAX = 32767;

using namespace std;

//functions prototype

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

//function definition

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

srand(time(NULL));

//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 << "*****************************************************" <<endl

<<"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

srand(time(NULL));

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

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

srand(time(NULL));

//RRowxCcolumns

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

}

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

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

insertionSort(a,n);

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

#include <cstdlib>

#include <iostream>

#include <vector>

#include <ctime>

#include <chrono>

#define RAND_MAX = 32767;

using namespace std;

//functions prototype

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

//function definition

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

srand(time(NULL));

//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 << "*****************************************************" <<endl

<<"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

srand(time(NULL));

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

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

srand(time(NULL));

//RRowxCcolumns

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

}

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

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

insertionSort(a,n);

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;

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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