@Sandeep,
If we do compaction then it becomes the same algo what Ankit suggested
earlier. Compaction will require 2 pass on the bigger array. Can we do it in
a single pass?
P.S. - I can not say for sure if doing it in one pass is really feasible. I
am still trying to work it out :-).
Thanks,
- Ravindra
On Wed, Jul 13, 2011 at 10:22 PM, Sandeep Jain <sandeep6...@gmail.com>wrote:
> @Ravindra: Since both the array contain m elements, you can assume that all
> elements lie from index [0] to index [m-1]
> However, because in your example we can consider 0, as a valid value of the
> sorted array.
>
> PS: Still, if you are suggesting that we should not consider 0 as a value.
> Then you can perform an compaction operation on 2nd array.
>
>
> Regards,
> Sandeep Jain
>
>
>
> On Wed, Jul 13, 2011 at 10:18 PM, ravindra patel <ravindra.it...@gmail.com
> > wrote:
>
>> @Bittu, Vaibhav
>> Can you please illustrate your algo for below arrays.
>>
>> Array1 - {1, 3, 5, 7}
>> Array2 - {0,0,0,2,0,4,6,8}
>>
>>
>> Thanks,
>> - Ravindra
>>
>>
>>
>> On Wed, Jul 13, 2011 at 9:47 PM, vaibhav shukla
>> <vaibhav200...@gmail.com>wrote:
>>
>>> start from the end of both the arrays... and try simple merge process not
>>> from the start but from where the last element is... and keep inserting the
>>> greater element at the end of the larger array.
>>>
>>>
>>> On Wed, Jul 13, 2011 at 8:41 PM, bittu <shashank7andr...@gmail.com>wrote:
>>>
>>>> @dumanshu check it
>>>>
>>>> Algo is simply start putting elemnt in bigger array by comparing then
>>>> from last logic is same as merge part of merg sort :)
>>>>
>>>> void merge(int[] a, int[] b, int n, int m)
>>>> {
>>>> int k = m + n - 1; // Index of last location of array b
>>>> int i = n - 1; // Index of last element in array b
>>>> int j = m - 1; // Index of last element in array a
>>>>
>>>> // Start comparing from the last element and merge a and b
>>>> while (i >= 0 && j >= 0)
>>>> {
>>>> if (a[i] > b[j])
>>>> {
>>>> a[k--] = a[i--];
>>>> }
>>>> else
>>>> {
>>>> a[k--] = b[j--];
>>>> }
>>>> }
>>>>
>>>> while (j >= 0)
>>>> {
>>>> a[k--] = b[j--];
>>>> }
>>>>
>>>> //no need to do for a array as its alraedy filled in B array :)
>>>>
>>>> }
>>>> Time O(N)
>>>>
>>>> Thanks
>>>> Shashank Mani Narayan
>>>> Computer Science & Engg.
>>>> Birla Institute of Technlogy Mesra
>>>>
>>>> --
>>>> 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.
>>>>
>>>>
>>>
>>>
>>> --
>>> best wishes!!
>>> Vaibhav Shukla
>>> DU-MCA
>>>
>>>
>>> --
>>> 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.
>>
>
> --
> 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.
