i = m-1
j = m-1
k = 2m-1
*compare (i,j) and put the maximum at k
if (i is max) decrement i;
if (j is max) decrement j
decrement k
*
and take care of boundary cases as well
On Fri, Jul 8, 2011 at 10:55 AM, ankit sambyal <ankitsamb...@gmail.com>wrote:
> @Sunny : Plz can u expain ur approach ??
>
>
> On Thu, Jul 7, 2011 at 10:11 PM, sunny agrawal <sunny816.i...@gmail.com>
> wrote:
> > @ankit
> > it can be done without shifting elements
> >
> > On Fri, Jul 8, 2011 at 9:52 AM, ankit sambyal <ankitsamb...@gmail.com>
> > wrote:
> >>
> >> Algo :
> >> Given array a[m] and b[2*m]
> >>
> >> 1. Shift the elements in the array b to the right half. Now the m
> >> elements in the array b are from index m to 2m-1
> >> 2. Initialize i (iterator of array a[]) =0
> >> j (iterator of array b[]) = m
> >> k (iterator of the final array which is b[]) = 0
> >> 3.
> >> while(1)
> >> {
> >> if(i==m)
> >> break;
> >> else if(j==2m)
> >> {
> >> Copy the remaining elements from array a[] into array b[]
> >> Then break;
> >> }
> >> else
> >> {
> >> if(a[i] < b[j])
> >> b[k++]=a[i++];
> >> else
> >> b[k++]=b[j++];
> >> }
> >> }
> >>
> >>
> >> Time Complexity : O(m)
> >> Space Complexity : O(1)
> >>
> >>
> >> On Thu, Jul 7, 2011 at 1:49 PM, sunny agrawal <sunny816.i...@gmail.com>
> >> wrote:
> >> > O(m) is always better than O(m^2) :) :P
> >> > Simple merge sort
> >> > hint : start from end of the arrays
> >> >
> >> > select the text in white font to see the hint :)
> >> >
> >> > On Fri, Jul 8, 2011 at 1:56 AM, Dumanshu <duman...@gmail.com> wrote:
> >> >>
> >> >> given two sorted arrays a[m] b[2*m], each contains m elements only.
> >> >> You
> >> >> need to merge those two arrays into second array b[2*m].
> >> >> anything better than O(m^2)????
> >> >>
> >> >> --
> >> >> 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.
> >> >>
> >> >
> >> >
> >> >
> >> > --
> >> > Sunny Aggrawal
> >> > B-Tech IV year,CSI
> >> > Indian Institute Of Technology,Roorkee
> >> >
> >> > --
> >> > 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.
> >>
> >
> >
> >
> > --
> > Sunny Aggrawal
> > B-Tech IV year,CSI
> > Indian Institute Of Technology,Roorkee
> >
> > --
> > 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.
>
>
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
