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.
Input: array with m+n elements (mPlusN[]).
NA => Value is not filled/available in array mPlusN[]. There should be n such array blocks.
Input: array with m+n elements (mPlusN[]).
Input: array with n elements (N[]).

Output: N[] merged into mPlusN[] (Modified mPlusN[])

#include<stdio.h>
#include<stdlib.h>
#define NA 10000 // say the biggest value exist.
// code for maintainind linked list.
// I have to perform insertion operation at end of the list.
// all the time I do not want to traverse the list till end to insert the element , so that I will maintain the last pointer called tail.
// head pointer pointind to the head of the list.
//the insertion operation will return the tail pointer , or pointer to the last inserted node , because when I insert the new element I do not want to traverse the entire list.
// In insert operation I need data to be inserted and pointer to the last node of the list.
struct node
{
int data;
struct node *link;
};
struct node * createNode(int data) // will return the pointer to the newely created node.
{
struct node *p=(struct node *)malloc(sizeof(struct node));
p->link=NULL;
p->data=data;
return p;
}
struct node *insert(struct node *p,int data)
{
struct node * temp=NULL;
temp=createNode(data);
if(p==NULL)// means my list is empty
{
return temp;
}
else
{
p->link=temp;
return temp;
}
}
// I will follow the same process as the mergeSort does.
// But in mergeSort I have to add both the list to the new list.
// Here I have to add the array to the given list.
int main(void)
{
int a[] = {2, 8, NA, NA, NA, 13, NA, 15, 20};
int b[] = {5, 7, 9, 25};
int arrSizeA=sizeof(a)/sizeof(a[0]);
int arrSizeB=sizeof(b)/sizeof(b[0]);
int i=0,j=0;
struct node *head=NULL,*tail=NULL,*temp=NULL;
while(j<arrSizeB) // while entire B array is scanned...
{
if(head!=NULL)
{
if((head->data) < b[j])
{
a[i]=head->data;
temp=head;
head=head->link;
free(temp);
i++;
if(head==NULL) // to see the list is empty or not , and if empty make teil NULL
{
tail=NULL;
}
}
}// end of outer if
if(b[j] < a[i])
{
if(a[i]==NA) // means there is no element in array a at ith location
{
if(a[i+1]<b[j]) // control jump into this outer if loop , when b[j]<a[i] , but for NA which is the bigger value this condition will always be true.
{
a[i]=a[i+1];
a[i+1]=NA;
i++;
}
else
{
a[i]=b[j];
i++;
j++;
}
}
else // I need to remove the element @ ith location in array a.
{
if(tail==NULL)
{
tail=insert(tail,a[i]);
head=tail; // update head if the element we are going to add is first element in the list.
}
else
{
tail=insert(tail,a[i]);
}
a[i]=b[j];
i++;
j++;
}
}// end of outer if
else // element in a is @ its right place.
{
i++;
}
}// end of while
// print the array.
printf("\ni==%d",i);
printf("\ni==%d \n",j);
for(i=0;i<arrSizeA;i++)
{
printf("-%d-",a[i]);
}
printf("\n");
return 0;
}
// all comments are invited
// please comment if the code do not work for some example.
No comments:
Post a Comment