Hello friends !
Problem statement :
We are given two sorted arrays , we have to create a new array from these two arrays and we need to insert elements in such a way that the newly created array remains sorted .
So, lets understand the logic with the code :
#include<stdio.h>
#include<stdlib.h>
#define max 100
void sort(int a[],int n);
void print(int a[],int n);
void merge(int a1[],int n1,int a2[],int n2);
int full[max];
int main()
{
int i,n1,a1[max];
printf("Enter the number of elements of first array : ");
scanf("%d",&n1);
printf("Enter array elements :\n");
for(i=0;i<n1;i++)
{
scanf("%d",&a1[i]);
}
int j,n2,a2[max];
printf("Enter the number of elements of second array : ");
scanf("%d",&n2);
printf("Enter array elements :\n");
for(j=0;j<n2;j++)
{
scanf("%d",&a2[j]);
}
//now we have two arrays
//lets sort them individually first
sort(a1,n1);
sort(a2,n2);
printf("First \n");
print(a1,n1);
printf("Second \n");
print(a2,n2);
merge(a1,n1,a2,n2);
printf("The merged \n");
print(full,n1+n2);
}
/* I have used insetion sort here for no reason,
one can use any random sorting algo for this
our prime aim is to merge two sorted arrays
such that resultant array is also sorted */
void sort(int a[],int n)
{
int i,temp;
int hole,value;
for(i=0;i<n;i++)
{
value = a[i];
hole = i ;
while(hole>0 && a[hole-1]>value)
{
a[hole] = a[hole-1];
hole--;
}
a[hole] = value;
}
}
void merge(int l[],int nl,int r[],int nr)
{
/*
We have two sorted array, say l[] and r[].
we have to fill array full[] such that
it should contains all elements of both l[] and r[]
and remain sorted*/
int i,j,k;
i=j=k=0;
while(i<nl && j<nr)
{
if(l[i] < r[j])
{
full[k++] = l[i++];
}
else
{
full[k++] = r[j++];
}
}
while(i<nl)
{
full[k++] = l[i++];
}
while(j<nr)
{
full[k++] = r[j++];
}
}
void print(int a[],int n)
{
int i;
printf("Sorted Array : ");
for(i=0;i<n;i++)
{
printf(" %d ",a[i]);
}
printf("\n");
}
Thanking you !
No comments :
Post a Comment