In: Computer Science
fix the code with constant expression error exrpession below in visual studio
#include <iostream>
#include <cstdlib>
#include <ctime>
void insertion_sort(int array[], int size, int start);
void heap_sort(int B[], int n);
void build_max_heap(int B[], int n);
void max_heapify(int B[], int i, int n);
void quick_sort(int B[], int p, int r);
int partition(int B[], int p, int r);
int main() {
int m = 10, Nf = 20000, Ns = 1000, delta = 1000,
A[m][Nf];
for (int i = 0; i < m; i++) {
for (int j = 0; j < Nf; j++)
{
A[i][j] = rand()
% 99 + 1;
// std::cout
<< A[i][j] << " ";
}
} std::cout << std::endl;
//----------------------------------------------------------------------------------------------
int ns = 1000, nf = 20000, mnf = m * nf,
randArray[mnf], counter1 = 0;
//create array with random numbers
for (int i = 0; i < m; i++) {
for (int j = 0; j < Nf; j++)
{
randArray[counter1] = rand() % 20000 + 1;
//std::cout
<< randArray[counter1] << " ";
counter1++;
}
}std::cout << std::endl;
//more variables
int copyArray[mnf], multiplier = 1;
clock_t t5, t6;
//----------------------------------------------------------------------------------------------
//calculations for ALG1
for (int n = ns; n <= nf; n = n + delta) {
//local variables
int timeAccu = 0, counter2 = 0,
timeAvg;
for (int i = 0; i < m; i++)
{
//copy randArray
for first n values of row i
for (int j = 0;
j < n; j++) {
copyArray[counter2] = randArray[counter2];
counter2++;
}
counter2 =
counter2 + Nf - (delta * multiplier);
t5 =
clock();
insertion_sort(copyArray, n, counter2 - Nf);
t6 = clock() -
t5;
timeAccu =
timeAccu + (int)t6;
}
multiplier++;
counter2 = 0;
timeAvg = timeAccu / m;
std::cout << "The average
runtime of ALG1 for " << n << " expressions is "
<< (float)timeAvg / 1000 << " ms" <<
std::endl;
std::cout << std::endl;
}
std::cout <<
"-------------------------------------------------------------------------------------------------------"
<< std::endl;
//int multiplier = 1;
clock_t t1, t2;
for (int n = Ns; n <= Nf; n = n + delta) {
int timeAccu = 0/*, counter =
0*/;
for (int i = 0; i < m; i++)
{
int *B = new
int[n];
for (int k = 0;
k < n; k++) {
B[k] = A[i][k];
}
//counter =
counter + Nf - (delta * multiplier);
t1 =
clock();
heap_sort(B, n -
1);
t2 = clock() -
t1;
timeAccu =
timeAccu + (int)t2;
if (i == 9
&& n == 20000){
for (int poo = 0; poo < n; poo++) {
// std::cout << B[poo]
<< " ";
}
}
}
std::cout << "The average
time for ALG2 for " << n << " expressions is " <<
(float)timeAccu / 10000 << " ms" << std::endl;
std::cout << std::endl;
}
std::cout <<
"-------------------------------------------------------------------------------------------------------"
<< std::endl;
//----------------------------------------------------------------------------------------------
for (int i = 0; i < m; i++) {
for (int j = 0; j < Nf; j++)
{
A[i][j] = rand()
% 99 + 1;
// std::cout
<< A[i][j] << " ";
}
} std::cout << std::endl;
//int multiplier = 1;
clock_t t3, t4;
for (int n = Ns; n <= Nf; n = n + delta) {
int timeAccu = 0/*, counter =
0*/;
for (int i = 0; i < m; i++)
{
int *B = new
int[n];
for (int k = 0;
k < n; k++) {
B[k] = A[i][k];
}
//counter =
counter + Nf - (delta * multiplier);
t3 =
clock();
quick_sort(B, 0,
n - 1);
t4 = clock() -
t3;
timeAccu =
timeAccu + (int)t4;
if (i == 9
&& n == 20000){
for (int poo = 0; poo < n; poo++) {
// std::cout << B[poo]
<< " ";
}
}
}
std::cout << "The average
time for ALG3 for " << n << " expressions is " <<
(float)timeAccu / 10000 << " ms" << std::endl;
std::cout << std::endl;
}
}
void insertion_sort(int array[], int size, int start) {
int i, key;
for (int j = start + 1; j < start + size; j++)
{
key = array[j];
i = j - 1;
while (i >= 0 &&
array[i] > key) {
array[i + 1] =
array[i];
i = i - 1;
}
array[i + 1] = key;
}
}
void heap_sort(int B[], int n) {
int temp;
build_max_heap(B, n);
for (int i = n; i >= 1; i--) {
temp = B[0];
B[0] = B[n];
B[n] = temp;
n = n - 1;
max_heapify(B, 0, n);
}
}
void build_max_heap(int B[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
max_heapify(B, i, n);
}
}
void max_heapify(int B[], int i, int n) {
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest, temp;
if (left <= n && B[left] > B[i]) {
largest = left;
}
else largest = i;
if (right <= n && B[right] > B[largest])
{
largest = right;
}
if (largest != i) {
temp = B[i];
B[i] = B[largest];
B[largest] = temp;
max_heapify(B, largest, n);
}
}
void quick_sort(int B[], int p, int r) {
int q;
if (p < r) {
q = partition(B, p, r);
quick_sort(B, p, q - 1);
quick_sort(B, q + 1, r);
}
}
int partition(int B[], int p, int r) {
int x = B[r];
int i = p - 1;
int temp1, temp2;
for (int j = p; j <= r - 1; j++) {
if (B[j] <= x) {
i = i + 1;
temp1 =
B[i];
B[i] =
B[j];
B[j] =
temp1;
}
}
temp2 = B[i + 1];
B[i + 1] = B[r];
B[r] = temp2;
return i + 1;
}
It worked for
me
#include <iostream>
#include <cstdlib>
#include <ctime>
void insertion_sort(int array[], int size, int start);
void heap_sort(int B[], int n);
void build_max_heap(int B[], int n);
void max_heapify(int B[], int i, int n);
void quick_sort(int B[], int p, int r);
int partition(int B[], int p, int r);
int main() {
int m = 10, Nf = 20000, Ns = 1000, delta = 1000, A[m][Nf];
for (int i = 0; i < m; i++) {
for (int j = 0; j < Nf; j++) {
A[i][j] = rand() % 99 + 1;
// std::cout << A[i][j] << " ";
}
} std::cout << std::endl;
//----------------------------------------------------------------------------------------------
int ns = 1000, nf = 20000, mnf = m * nf, randArray[mnf], counter1 =
0;
//create array with random numbers
for (int i = 0; i < m; i++) {
for (int j = 0; j < Nf; j++) {
randArray[counter1] = rand() % 20000 + 1;
//std::cout << randArray[counter1] << " ";
counter1++;
}
}std::cout << std::endl;
//more variables
int copyArray[mnf], multiplier = 1;
clock_t t5, t6;
//----------------------------------------------------------------------------------------------
//calculations for ALG1
for (int n = ns; n <= nf; n = n + delta) {
//local variables
int timeAccu = 0, counter2 = 0, timeAvg;
for (int i = 0; i < m; i++) {
//copy randArray for first n values of row i
for (int j = 0; j < n; j++) {
copyArray[counter2] = randArray[counter2];
counter2++;
}
counter2 = counter2 + Nf - (delta * multiplier);
t5 = clock();
insertion_sort(copyArray, n, counter2 - Nf);
t6 = clock() - t5;
timeAccu = timeAccu + (int)t6;
}
multiplier++;
counter2 = 0;
timeAvg = timeAccu / m;
std::cout << "The average runtime of ALG1 for " << n
<< " expressions is " << (float)timeAvg / 1000 <<
" ms" << std::endl;
std::cout << std::endl;
}
std::cout <<
"-------------------------------------------------------------------------------------------------------"
<< std::endl;
//int multiplier = 1;
clock_t t1, t2;
for (int n = Ns; n <= Nf; n = n + delta) {
int timeAccu = 0/*, counter = 0*/;
for (int i = 0; i < m; i++) {
int *B = new int[n];
for (int k = 0; k < n; k++) {
B[k] = A[i][k];
}
//counter = counter + Nf - (delta * multiplier);
t1 = clock();
heap_sort(B, n - 1);
t2 = clock() - t1;
timeAccu = timeAccu + (int)t2;
if (i == 9 && n == 20000){
for (int poo = 0; poo < n; poo++) {
// std::cout << B[poo] << " ";
}
}
}
std::cout << "The average time for ALG2 for " << n
<< " expressions is " << (float)timeAccu / 10000
<< " ms" << std::endl;
std::cout << std::endl;
}
std::cout <<
"-------------------------------------------------------------------------------------------------------"
<< std::endl;
//----------------------------------------------------------------------------------------------
for (int i = 0; i < m; i++) {
for (int j = 0; j < Nf; j++) {
A[i][j] = rand() % 99 + 1;
// std::cout << A[i][j] << " ";
}
} std::cout << std::endl;
//int multiplier = 1;
clock_t t3, t4;
for (int n = Ns; n <= Nf; n = n + delta) {
int timeAccu = 0/*, counter = 0*/;
for (int i = 0; i < m; i++) {
int *B = new int[n];
for (int k = 0; k < n; k++) {
B[k] = A[i][k];
}
//counter = counter + Nf - (delta * multiplier);
t3 = clock();
quick_sort(B, 0, n - 1);
t4 = clock() - t3;
timeAccu = timeAccu + (int)t4;
if (i == 9 && n == 20000){
for (int poo = 0; poo < n; poo++) {
// std::cout << B[poo] << " ";
}
}
}
std::cout << "The average time for ALG3 for " << n
<< " expressions is " << (float)timeAccu / 10000
<< " ms" << std::endl;
std::cout << std::endl;
}
}
void insertion_sort(int array[], int size, int start) {
int i, key;
for (int j = start + 1; j < start + size; j++) {
key = array[j];
i = j - 1;
while (i >= 0 && array[i] > key) {
array[i + 1] = array[i];
i = i - 1;
}
array[i + 1] = key;
}
}
void heap_sort(int B[], int n) {
int temp;
build_max_heap(B, n);
for (int i = n; i >= 1; i--) {
temp = B[0];
B[0] = B[n];
B[n] = temp;
n = n - 1;
max_heapify(B, 0, n);
}
}
void build_max_heap(int B[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
max_heapify(B, i, n);
}
}
void max_heapify(int B[], int i, int n) {
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest, temp;
if (left <= n && B[left] > B[i]) {
largest = left;
}
else largest = i;
if (right <= n && B[right] > B[largest]) {
largest = right;
}
if (largest != i) {
temp = B[i];
B[i] = B[largest];
B[largest] = temp;
max_heapify(B, largest, n);
}
}
void quick_sort(int B[], int p, int r) {
int q;
if (p < r) {
q = partition(B, p, r);
quick_sort(B, p, q - 1);
quick_sort(B, q + 1, r);
}
}
int partition(int B[], int p, int r) {
int x = B[r];
int i = p - 1;
int temp1, temp2;
for (int j = p; j <= r - 1; j++) {
if (B[j] <= x) {
i = i + 1;
temp1 = B[i];
B[i] = B[j];
B[j] = temp1;
}
}
temp2 = B[i + 1];
B[i + 1] = B[r];
B[r] = temp2;
return i + 1;
}
See The
Output
If it doesnt work try to run it online C++ compiler and it
works