In Java Language 1. Consider two arrays A and B, each storing n different intege

ID: 3581616 • Letter: I

Question

In Java Language

1. Consider two arrays A and B, each storing n different integer values. All values in A and B are different. In both arrays the values are sorted in increasing order. Write an algorithm that merges A and B and stores their values in an array C in such a way that the first n values in C are sorted in increasing order and the last n values are sorted in decreasing order.

For example, if A and B are as follows:

You cannot use any auxiliary data structures and you must write the complete algorithm (you cannot invoke algorithms for which you do not provide pseudocode).

2. Compute the time complexity of your algorithm in the worst case. Explain how you computed the time complexity and give the order of the time complexity.

THANK YOU :)

A 3 6 13 19 B 1 4 9 11 17 0 2 4 0 2 4 Then array C must be this: 1 3 4 6 8 19 17 13 11 9 0 1 2 3 4 5 7 8 9

Explanation / Answer

package snippet;

public class MergeArray {


   public static int[] merge(int[] a, int[] b) {

   int[] c = new int[a.length + b.length];
   int i = 0, j = 0, k = 0;
   while (i <=a.length/2 && j <=b.length/2)
   {
   if (a[i] < b[j])
   {
   c[k] = a[i];
   i++;
   }
   else
   {
   c[k] = b[j];
   j++;
   }
   k++;
   }
   i =a.length-1;
   j=b.length-1;
   while (i >a.length/2 && j >b.length/2)
   {
   if (a[i] > b[j])
   {
   c[k] = a[i];
   i--;
   }
   else
   {
   c[k] = b[j];
   j--;
   }
   k++;
   }

   while (i >a.length/2)
   {
   c[k] = a[i];
   i--;
   k++;
   }

   while (j >=b.length/2)
   {
   c[k] = b[j];
   j--;
   k++;
   }

return c;
}

   public static void main(String[] args) {
       // TODO Auto-generated method stub

       int ans[]=new int[10];

       int a[]={3,6,8,13,19};
       int b[]={1,4,9,11,17};
       ans=merge(a, b);
       for(int i=0;i<ans.length;i++)
       {
           System.out.println(ans[i]+" ");
       }

}

======================================================================

Output:

1
3
4
6
8
19
17
13
11
9

====================================================================

Time complexity is O(n+n);

As first loop stores in increasing order from 0 to mid of length And another loop from length to mid.Hence ,its complexity is O(n)

Navigate

In Java Index of Coincidence If two strings of equal length are superimposed on

In Java Language 1. Write a recursive method expFive(n) to compute y=5^n. For in

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

In Java Language 1. Consider two arrays A and B, each storing n different intege

Question

Explanation / Answer

Related Questions

Navigate