Merge

QUESTION

There are two sorted arrays. First one is of size m+n containing only m elements. Another one is of size n and contains n elements. Merge these two arrays into the first array of size m+n such that the output is sorted.\n\nInput:\nThe first line contains the size of m+n array.\nThe second line contains elements of m+n array.The elements with \”-1\” denotes the vacant spaces to be filled.\nThe third line contains size of n array.\nThe fourth line contains the size of the n array.\n\nOutput:\nOutput contains m+n arrays in sorted order.

“TESTCASE_1”: “5\n4 5 -1 -1 7\n2\n8 10\n###—###SEPERATOR—###—\n4 5 7 8 10”, “TESTCASE_2”: “6\n7 -1 -1 10 -1 -1\n4\n9 8 13 12\n###—###SEPERATOR—###—\n7 8 9 10 12 13”, “TESTCASE_3”: “4\n1 -1 -1 9\n2\n80 98 \n###—###SEPERATOR—###—\n1 9 80 98”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <stdio.h>

/* Assuming -1 is filled for the places where element
   is not available */


/* Function to move m elements at the end of array mPlusN[] */
void moveToEnd(int mPlusN[], int size)
{
  int i = 0, j = size - 1;
  for (i = size-1; i >= 0; i--)
    if (mPlusN[i] != -1)
    {
      mPlusN[j] = mPlusN[i];
      j--;
    }
}

/* Merges array N[] of size n into array mPlusN[]
   of size m+n*/
int merge(int mPlusN[], int N[], int m, int n)
{
  int i = n;  /* Current index of i/p part of mPlusN[]*/
  int j = 0; /* Current index of N[]*/
  int k = 0; /* Current index of of output mPlusN[]*/
  while (k < (m+n))
  {
    /* Take an element from mPlusN[] if
       a) value of the picked element is smaller and we have
          not reached end of it
       b) We have reached end of N[] */
    if ((i < (m+n) && mPlusN[i] <= N[j]) || (j == n))
    {
      mPlusN[k] = mPlusN[i];
      k++;
      i++;
    }
    else  // Otherwise take element from N[]
    {
      mPlusN[k] = N[j];
      k++;
      j++;
    }
  }
}

/* Utility that prints out an array on a line */
void printArray(int arr[], int size)
{
  int i,temp,j;
 
  for(i=0;i<size;i++)
  {
    for(j=i+1;j<size;j++)
    {
      if(arr[i]>arr[j])
      {
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
      }
    }
  }
 for (i=0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

/* Driver function to test above functions */
int main()
{
  /* Initialize arrays */
 int mp,i,n1,n,m;
  scanf("%d",&mp);
  int mPlusN[mp];
  for(i=0;i<mp;i++)
    scanf("%d",&mPlusN[i]);
  scanf("%d",&n1);
  int N[n1];
  for(i=0;i<n1;i++)
    scanf("%d",&N[i]);
  n = sizeof(N)/sizeof(N[0]);
  m = sizeof(mPlusN)/sizeof(mPlusN[0]) - n;

  /*Move the m elements at the end of mPlusN*/
  moveToEnd(mPlusN, m+n);

  /*Merge N[] into mPlusN[] */
  merge(mPlusN, N, m, n);

  /* Print the resultant mPlusN */
  printArray(mPlusN, m+n);
  

  return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro