size of a=m size of b =n
a[]={1,3,77,78,90} and b[]={2,5,79,81}
l r
while(l<=m && r<=n)
{
if(b[r]<a[l])
{
swap(a[l],b[r]);
l++;
sort(b[]);
}
elseif(a[l]<b[r])
l++;
}
On Fri, Jul 8, 2011 at 6:47 PM, Apoorve Mohan <apoorvemo...@gmail.com>wrote:
> @aman: wat u dint get???
>
>
> On Fri, Jul 8, 2011 at 6:34 PM, Aman Goyal <aman.goya...@gmail.com> wrote:
>
>> i dint get you..
>>
>> one loop to access the first array elements and compare with second array,
>> and one logn (for) loop to binary search the second array , thts it..
>> O(mlogn) is what i am able to understand.
>>
>> On Fri, Jul 8, 2011 at 5:52 PM, Apoorve Mohan <apoorvemo...@gmail.com>wrote:
>>
>>> @aman:
>>>
>>> Let size of *first array be m* and that of the *second array be* *n*.
>>>
>>> For m elements in first array you perform binary search therefore time
>>> O(mlogn)
>>>
>>> And for those some elements of the first array you perform shifting in
>>> array two...in the worst case for all the elements of first array
>>> you might have to perform shifting in second array and also you might
>>> just have to shift all the present (n-1) elements each time...so again in
>>> worst case this whole procedure will take O(mn) time....
>>>
>>> so total coplexity of your idea is: O(mlogn) + O(mn)
>>>
>>> And if m is of the O(n) then this will take O(n^2) time in worst case.
>>>
>>>
>>> On Fri, Jul 8, 2011 at 2:40 PM, Aman Goyal <aman.goya...@gmail.com>wrote:
>>>
>>>> Algo:
>>>>
>>>>
>>>> 1 3 77 78 90
>>>> 2 5 79 81
>>>>
>>>> compare 1 &2 =1
>>>> compare 3 &2 =2 and call binary search on 2nd array widot 2 to identify
>>>> a proper position for 3 and place it there.
>>>> now arrays
>>>>
>>>> 1 2 77 78 90
>>>> 3 5 79 81
>>>> 3 and 77= swap + binary
>>>>
>>>> compare 3 and 77, swap them
>>>> find position of 77 in second array and place there. using binary search
>>>>
>>>> 1 2 3 78 90
>>>> 5 77 79 81
>>>> 78 and 5 = swap + binary search
>>>>
>>>> 1 2 3 5 90
>>>> 77 78 79 81
>>>>
>>>> 90 and 77= swap+ binary
>>>>
>>>>
>>>> 1 2 3 5 77
>>>> 78 79 81 90
>>>>
>>>> ans found
>>>>
>>>> O(nlogn)
>>>> binary search is O(logn) .
>>>>
>>>>
>>>> On Fri, Jul 8, 2011 at 8:29 AM, durgesh kumar <durgesh1...@gmail.com>wrote:
>>>>
>>>>>
>>>>> @dumanshu
>>>>>
>>>>> > ok ! i got a O(n lgn) finally
>>>>> > i don know exact complexity
>>>>> > Let N = size of first array
>>>>> > Find the first N smallest elements using one pointer in each array
>>>>> > now swap the list of elements from index 0 to second-pointer in
>>>>> > second array to first array
>>>>> > with first_poiner+1 to N in first Array
>>>>> > now,after swapnig we need to sort both array
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> so complexity= n + n log n+ m log m (n is the size of of first array
>>>>> and m is the size of second array)
>>>>> .
>>>>> . . O(n) = (n log n ) or (m log m)
>>>>> thanks
>>>>> Durgesh
>>>>>
>>>>> --
>>>>> 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.
>>>>
>>>
>>>
>>>
>>> --
>>> regards
>>>
>>> Apoorve Mohan
>>>
>>>
>>> --
>>> 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.
>>
>
>
>
> --
> regards
>
> Apoorve Mohan
>
> --
> 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.
