Algorithm analysis help answer part b only please let me know how sure you are a

Question

Algorithm analysis help

answer part b only

please let me know how sure you are about the answe

Problem 7.13. The use of sentinels in algorithm merge requires the availability of an additional cell in the arrays to be merged; see Section 7.4.1. Although this is not an issue when merge is used within mergesort, it can be a nuisance in other applications. More importantly, our merging algorithm can fail if it is not possible to guarantee that the sentinels are strictly greater than any possible value in the arrays to be merged. (a) Give an example of arrays U and V that are sorted but where the result of merge(U, V, T) is not what it should be. What is the contents of T after this pathological call? (You are allowed the value infinity in arrays U and V and you may wish to specify the values of U and V outside the bounds of the arrays.) (b) Give a procedure for merging that does not use sentinels. Your algorithm must work correctly in linear time provided the arrays U and V are sorted prior to the call.

Explanation / Answer

#include <stdio.h>
#define ARRAY_SIZE 5

void MergeSort(int arr[],int p,int r);
void Merge(int arr[],int p,int q,int r);

int main(void)
{
int array[ARRAY_SIZE];
int i;
printf(" Enter the Array elements : ");
for(i=0;i<ARRAY_SIZE;i++)
{
scanf("%d",&array[i]);
}

/*calling MergeSort()*/
MergeSort(array,0,ARRAY_SIZE-1);

/*After sorting, printing the array elements*/
printf(" After sorting array elements :");
for(i=0;i<ARRAY_SIZE;i++)
{
printf(" %d ",array[i]);
}
return 0;
}

/*It does the merge-sort on the array
*p is the starting index of array
*r is the ending index of array*/
void MergeSort(int arr[],int p,int r)
{
int q;
if(p<r)
{
q = (r+p)/2;
MergeSort(arr,p,q);
MergeSort(arr,q+1,r);
Merge(arr,p,q,r);
}
}

/*Merge() does the merging of two sorted subarrays.
*arr[p..q] and arr[q+1..r] are the two sorted arrays.
*It does the marging without using sentinales*/
void Merge(int arr[],int p,int q,int r)
{
int *L,*R;
int i = 0,j=0,n1,n2,k=p;

n1 = q-p+1;
n2 = r - q;
L = malloc(sizeof(int)*n1);
R = malloc(sizeof(int)*n2);

for(i=0;i<n1;i++)
L[i] = arr[p+i];
for(j=0; j<n2;j++)
R[j] = arr[q+j+1];

/*reset i and j*/
i = 0;
j = 0;
/*merging the items in sorted order
*till we find end of any array L or R*/
while(i<n1 && j<n2)
{
if(L[i]<R[j])
{
arr[k] = L[i];
i = i+1;
}
else
{
arr[k] = R[j];
j = j+1;
}
k++;
}

/*check whether any array has some elements left
*if some items left then put them to the final O/P array*/
if(i!=n1)
for(;i<n1;i++){
arr[k] = L[i];
k++;
}
else if(j!=n1)
for(;j<n2;j++){
arr[k] = R[j];
k++;
}
free(L);
free(R);
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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