Write a program in C++ to do the following: Your program should perform the foll

Question

Write a program in C++ to do the following: Your program should perform the following:

a. Randomly generate three integer arrays A1, A2, and A3 of sizes N=103 , 105 , and 107 (or 106 , if your computer cannot handle an integer array of size 107 ), in that order.

b. Run all the four sorting algorithms (insertion, merge, heap and quick sort) we’ve learned in class on each of the three arrays A1, A2 and A3, and record the number of comparisons between array elements and actual elapsed times in appropriate time units, for instance, milliseconds.

c. Repeat b on the sorted arrays A1, A2 and A3.

d. Reverse the order of the three arrays A1, A2 and A3 and repeat b once more.  

Explanation / Answer

Solution:

code:

#include<iostream>
#include<cstdlib>
#include<vector>
using namespace std;
int maxSumRec(const vector<int> & a, int left, int right);
int maxSubSum3(const vector<int> &a);
int max3(int a,int b, int c);
int max(int a, int b);

int num21,num29;
main()
{
int n,j, max_sum, num, c;
vector <int> a;
int size[5]={101,103,105,107,109};
for(int i=0;i<5;i++)
{
for ( j=0 ; j<size[i] ; j++ )
{
num = (rand()%100)-50;
a.push_back(num);
// cout<<a[j]<<endl;
}
max_sum=maxSubSum3(a);
cout<<"No of times line 21 executed ="<<num21<<endl;
cout<<"No of times line 29 executed ="<<num29<<endl;
a.clear();
}
return 0;
}
int maxSubSum3(const vector<int> &a)
{
num21=0;
num29=0;
return maxSumRec(a,0,a.size()-1);
}
int maxSumRec(const vector<int> & a, int left, int right)
{
if(left == right)
if(a[left]>0)
return a[left];
else return 0;
  
int center = (left+right)/2;
int maxLeftSum = maxSumRec(a,left,center);
int maxRightSum= maxSumRec(a,center+1,right);
  
int maxLeftBorderSum=0,leftBorderSum=0;
for(int i=center;i>=left;--i)
{
leftBorderSum+=a[i];
num21++;
if(leftBorderSum>maxLeftBorderSum)
maxLeftBorderSum=leftBorderSum;
  
}
  
int maxRightBorderSum =0, rightBorderSum =0;
for(int i=center+1;i<=right;i++)
{
rightBorderSum+=a[i];
num29++;
if(rightBorderSum>maxRightBorderSum)
maxRightBorderSum=rightBorderSum;
}
  
return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);
}
int max3(int a,int b, int c)
{
return max(max(a,b),c);
}
int max(int a, int b)
{
return a>b? a:b;
  
}

Output:

N log N for each 101,103,105,107,109 = { 202.4364, 207.3222, 212.2248, 217.144, 222,0795}

number of times executed for each value of N = { 680, 696, 712, 728,744}

N log N / no of times executed for each N = { 0.2977 , 0.2978, 0.2980, 0.2982, 0.2985}

all the values are almost equal hence we can say it is a N log N time algorithm

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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