Consider the following class: that creates a new sequence, appending this and th

Question

Consider the following class: that creates a new sequence, appending this and the other sequence, without modifying either sequence. For example, if a is 1 4 9 16 and b is the sequence 9 7 4 9 11 then the call a.append(b) returns the sequence 149 16 9749 11 without modifying a or b. Add a method that merges two sequences, alternating elements from both sequences. If one sequence is shorter than the other, then alternate as long as you can and then append the remaining elements from the longer sequence. For example, if a is 1 4 9 16 and b is 9 7 4 9 11 then a.merge(b) returns the sequence 194794 16 9 11 without modifying a or b. Add a method that merges two sorted sequences, producing a new sorted sequence. Keep an index into each sequence, indicating how much of it has been processed already. Each time, append the smallest unprocessed value from either sequence, then advance the index. For example, if a is 1 4 9 16 and b is 479911 then a.mergeSorted(b) returns the sequence 144799911 16 without modifying a or b..

Explanation / Answer

void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

/* create temp arrays */
int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */
for(i = 0; i < n1; i++)
L[i] = arr[l + i];
for(j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

/* Copy the remaining elements of L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

/* l is for left index and r is right index of the sub-array
of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2; //Same as (l+r)/2, but avoids overflow for large l and h
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}


/* UITLITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf(" ");
}

/* Driver program to test above functions */
int main()
{
int a[]={1,9,7};
int b[]={12, 11, 13, 5, 6, 7};
int arr[] = new int[a.length+b.length];
int c=0;
for(int i=0;i<a.length;i++)
{
arr[i]=a[i];
c++;
}
for(int j=0;j<b.length;j++)
{
arr[c++]=b[j];
}
for(int i=0;i<c.length;i++)
printf(arr[i]+" ");

int arr_size = sizeof(arr)/sizeof(arr[0]);

printf("Given array is ");
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf(" Sorted array is ");
printArray(arr, arr_size);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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