In this assignment, you are given two functions merge and mergesort. You are req
ID: 3689742 • Letter: I
Question
In this assignment, you are given two functions merge and mergesort. You are required to do the following:
1) Modify as necessary both functions (merge and mergesort) such that mergesort returns the total number of comparisons that have performed in sorting a given array a. In these comparisons, only the comparisons that involve array elements are counted. You are not allowed to use any global variable in counting these comparisons. You may want to add new parameters to functions and/or make functions return integer values.
2) Write a C++ program that receives as input an array of integers and calls mergesort to sort this array. Output must include the final sorted array and number of comparisons performed as described in Item 1 above.
One input to your program is the following:
21 3 5 7 26 18 20 11 25 17 27 9 30 24 16 28 14 5 19 23 6 29 4 13 18 22 10 8
void merge(int a[], int l, int m, int r)
{ int i, j;
static int aux[maxN];
for (i = m+1; i > l; i--) aux[i-1] = a[i-1];
for (j = m; j < r; j++) aux[r+m-j] = a[j+1];
for (int k = l; k <= r; k++)
if (aux[j] < aux[i])
a[k] = aux[j--]; else a[k] = aux[i++];
}
void mergesort(int a[], int l, int r)
{ if (r <= l) return;
int m = (r+l)/2;
mergesort(a, l, m);
mergesort(a, m+1, r);
merge(a, l, m, r);
}
Explanation / Answer
Answer:
1)
void mergesort(int a[], int l, int r){
if(l < r){
int m = (l+r)/2;
mergesort(a,l, m);
mergesort(a,m+1,r);
merge(a, l,m, m+1, r);
}
}
void merge(int a[], int lf, int ll, int rf, int rl)
{
int count=0;
static int aux[maxN];
int i = lf;
int saveFirst = lf;
while((lf <= ll) && ( rf <= rl))
{
if(a[lf] < a[rf])
{
aux[i] = a[lf];
lf++;
}
else
{
aux[i] = a[rf];
rf++;
}
i++;
count++;
}
while(lf <= ll)
{
aux[i] = a[lf];
lf++;
i++;
}
while(rf <= rl)
{
aux[i] = a[rf];
rf++;
i++;
}
}
2)
#include < iostream >
#include < stdio.h >
using namespace std;
int count = 0;
int n = 0;
const int MaxN= 100;
void merge(int a[], int lf, int ll, int rf, int rl);
void displayarray(int a[], int n);
void merge(int a[], int lf, int ll, int rf, int rl)
{
static int aux[maxN];
int i = lf;
int holdfirstelement = lf;
while((lf <= ll) && ( rf <= rl))
{
if(a[lf] < a[rf])
{
aux[i] = a[lf];
lf++;
}
else
{
aux[i] = a[rf];
rf++;
}
i++;
count++;
}
while(lf <= ll)
{
aux[i] = a[lf];
lf++;
i++;
}
while(rf <= rl)
{
aux[i] = a[rf];
rf++;
i++;
}
for(i= holdfirstelement; i<= rightLast; i++)
a[i] = aux[i];
displayarray(a,n);
cout << endl;
}
void displayarray( int a[], int n){
cout<<"The array which is sorted is :"<<endl;
for (int i=0; i < n; i++)
cout << a[i] << " ";
}
int main(){
cout << "Enter number of elements : ";
cin >>n;
int a[MaxN];
for (int i=0; i < n; i++){
if(i==0)
cout << "Enter the first element: ";
else
cout << "Enter the next element: ";
cin >> a[i];
}
int l = 0;
int r = n-1;
mergesort(a, l, r);
displayarray(a, n);
cout << endl;
cout << "Number of comparisons are : "<< count << endl;
}