hmm ya u need an extra K array but i think soln is fast do U
On Mon, Feb 7, 2011 at 3:11 PM, jalaj jaiswal <jalaj.jaiswa...@gmail.com>wrote:
> for merge sort extra space will be needed
>
>
> On Mon, Feb 7, 2011 at 3:10 PM, arpit busy in novels <
> arpitbhatnagarm...@gmail.com> wrote:
>
>> Hey i m just a newbie To group BTW from MNIT jaipur 3rd yr CS
>>
>> I just though we should apply merge sort < mean merge 2 array into one )
>> on 1st row & 1st column <this will be accurate since rows & columns r
>> Sorted) next we move down the diagnol 1 step & apply the same merge sort
>> n so on < cant say much abt complexity but it feels effective)
>>
>>
>>
>> for (i=0,j=0;i<n& j<n)
>> {
>> k[]=merge ( a[0,0] row & column)
>> i++,j++;
>> }
>>
>>
>>
>>
>>
>> On Mon, Feb 7, 2011 at 2:49 PM, jalaj jaiswal
>> <jalaj.jaiswa...@gmail.com>wrote:
>>
>>> isn't mnlog(mn)(simple quick sorting the entire array) better then
>>> mnlog(m+n)
>>>
>>>
>>>
>>> On Mon, Feb 7, 2011 at 2:46 PM, sunny agrawal
>>> <sunny816.i...@gmail.com>wrote:
>>>
>>>> one of the possible methods is to use concept same as EXTRACT-MIN of
>>>> heaps
>>>>
>>>> do the following steps *m*n *times
>>>> 1. print a[0][0] ans replace this by a[m-1][n-1]
>>>> 2. call REORDER(0,0)
>>>>
>>>> in REORDER(i,j) function we perform following operations to make array's
>>>> all row's and column's sorted
>>>> 1.if a[i,j] <= a[i+1][j] && a[i,j] <= a[i][j+1], its done
>>>> else swap with min a[i+1,j] and a[i,j+1] and keep going in same way
>>>>
>>>> ans also boundary checks are also important...
>>>>
>>>> TC: O(mn(m+n))
>>>> SC: O(1)
>>>>
>>>> --
>>>> 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.
>>>>
>>>
>>>
>>>
>>> --
>>> With Regards,
>>> *Jalaj Jaiswal* (+919019947895)
>>> Software developer, Cisco Systems
>>> Final Year Undergraduate,
>>> IIIT ALLAHABAD
>>>
>>> --
>>> 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.
>>>
>>
>>
>>
>> --
>> Arpit Bhatnagar
>> (MNIT JAIPUR)
>>
>> --
>> 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.
>>
>
>
>
> --
> With Regards,
> *Jalaj Jaiswal* (+919019947895)
> Software developer, Cisco Systems
> Final Year Undergraduate,
> IIIT ALLAHABAD
>
> --
> 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.
>
--
Arpit Bhatnagar
(MNIT JAIPUR)
--
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.
