Monday, February 16, 2015

Merge an array of size n into another array of size m+n

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[]).
MergemPlusNNA => Value is not filled/available in array mPlusN[]. There should be n such array blocks.
Input: array with n elements (N[]).
MergeN
Output: N[] merged into mPlusN[] (Modified mPlusN[])
MergemPlusN_Res




#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