RUN


Input: arr1 = {1,3,5,7} and arr2 = {2,4,6,8,10} 

Output: {1,2,3,4,5,6,7,8,10}

Explanation: The problem statement is quite simple to understand. The input contains two sorted arrays and the output is the merged resultant of these two arrays. The approach to solving this problem is using the idea of a merge sort to merge these arrays. For this, we use an output array to store the merge result of the input arrays.

Algorithm :

  1. Create an output array of the sum of the size of both the given arrays.
  2. Iterate through the given arrays together, and compare the elements of both the arrays with each other. Store the smaller element in the output array. Then increment the positions of the output array.
  3. Finally, the remaining elements in the given arrays are appended at the end of the output array.

Code:

#include<iostream> 
using namespace std; 

void merge_two_arrays(int a1[], int a2[], int l1, int l2, int op[]) 
{ 
    int i1 = 0, i2 = 0, i3 = 0; 
    while (i1 < l1 && i2 < l2) 
    { 
        if (a1[i1] < a2[i2]) 
        {
            op[i3] = a1[i1]; 
            i3++;
            i1++;
        }
        else
        {
            op[i3] = a2[i2]; 
            i3++;
            i2++;
        }
    } 

    while (i1 < l1) 
    {
       op[i3] = a1[i1]; 
       i3++;
       i1++;
    }    

    while (i2 < l2) 
    {
       op[i3] = a2[i2]; 
       i3++;
       i2++;
    }
}

int main(){

    int a1[100],a2[100],l1,l2,i;
    cout<<"Enter size of array 1: "<<endl;
    cin>>l1;
    cout<<"Enter array elements: "<<endl;
    
    for(i=0;i<l1;i++)
    {
        cin>>a1[i];
    }

    cout<<"Enter size of array 2: "<<endl;
    cin>>l2;
    cout<<"Enter array elements: "<<endl;

    for(i=0;i<l2;i++)
    {
        cin>>a2[i];
    }

    int op[l1+l2]; 
    merge_two_arrays(a1, a2, l1, l2, op); 
    cout << "Resultant array after merging two sorted arrays:" <<endl; 
   
   for (i=0; i < l1+l2; i++) 
    {
        cout<<op[i]<<" "; 
    }
    return 0;
}

Output: 

Enter size of array 1:
4
Enter array elements:
1
3
5
7
Enter size of array 2:
5
Enter array elements:
2
4
6
8
10
Resultant array after merging two sorted arrays:
1 2 3 4 5 6 7 8 10

Time Complexity: O(l1+l2)
Space Complexity: O(l1+l2)

Report Error/ Suggestion

Related Posts:




CopyRight © 2020

CopyRight © 2020