Re: [algogeeks] In Place Merging of Two Sorted .Array...Not Easy as seems to be,....

[ankit sambyal]

Hey, it can be done in o(n*logn) time by calling maxheapify function on the
two arrays. Then it decreases the size of the array whose last element is
maximum of the two arrays. I hope you are aware of heap data structure and
you have got the idea how to do it. If not let me know, it will explain it.
Though its not O(n) but still better than o(n^2). I will think of O(n)
solution.


regards,
Ankit





On Fri, Feb 25, 2011 at 5:36 AM, bittu shashank7andr...@gmail.com wrote:

 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;jbs-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 algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] In Place Merging of Two Sorted .Array...Not Easy as seems to be,....

[bittu]

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;jbs-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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.