we have two sorted array a[]={2,6,9,60}; b[]={1,3,5,34,80}; merge the
array in such way..
a[]={1,2,3,5}; b[]={6,9,34,60,80}; ..no extra space is allowed..i.e.
In-Place merging
Many of you thinks its easy..but here is q. of minimum complexity i
have done this but min e complexity high that not seems to be gud..i
know it can be done O(n) I have tried in O(n^2)...so i looking for
some gud solution for this
here is my approach lets take two array bigger & smaller
void merge(int[] smaller, int[] bigger)
{
int ls=smaller.length;
int bs=bigger.length;
while(true)
{
if(smaller[ls-1]<=bigger[0])
{
break;
}
//swap
int z=smaller[ls-1];
smaller[ls-1]=bigger[0];
bigger[0]=z;
//sort small
for(int j=ls-2; j>=0;j--)
{
if(smaller[j]<smaller[j+1])
{
break;
}
int s=smaller[j+1];
smaller[j+1]=smaller[j];
smaller[j]=s;
}
//sort bigger
for(int j=0;j<bs-1;j++)
{
if(bigger[j]<bigger[j+1])
{
break;
}
int s=bigger[j+1];
bigger[j+1]=bigger[j];
bigger[j]=s;
}
}
}
Correct me if anything missing or wrong i can improve complexity ???
Hurray up!!!!!!!
Thanks & Regards
Shashank >>"The Best Way to Escape From The Problem is ton solve it"
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
