@All..
I have an idea...
As we are looking for an in-place algo...
Well, given the array, it actually mimics a min-heap.. not exactly a
binary tree heap but a heap wherein its subtrees share some nodes...
Now the point being that... say we select any index pair (i,j), we
know for the submatrix whose left-top corner is (i,j) and right-bottom
corner is (m,n) , he smallest element among all the elements in the
submatrix is positioned at (i,j) itself.. Same goes for largest
element which is positioned at (m,n).. Hence we can say that any
submatrix rooted at (i,j) acts as a min-heap...
Now, say if i replace A(i,j) with a value greater than A(i,j), then
heapifying the submatrix so that the sorted(row,col) order is restored
will take (m + n -i -j) max steps...basically either go down or go
left in case adjustment is required...
Keeping in mind the above heapifying property lets solve the actual
problem row wise...
Pseudocode:
for ( int row = 0; row < N; ++row)
for (int col =0; col < N; ++col)
{
if (A[row][col] > A[row+1][0])
{
swap (A[row][col] , A[row+1][0])
heapify/readjust (submatrix rooted at A[row+1][0] )
}
}
I think the above shall work...
What do u guys think??
Say, no of rows = m and no. of cols = n,
Time complexity = sum over all i (1 to M} { i*(M+N-i) }
= O(M^3) ...
In case M > N,
then we can follow the same process column-wise and the time
complexity would be O(N^3)..
On Jan 11, 1:35 pm, Sanjay Rajpal <sanjay.raj...@live.in> wrote:
> Where do we store the sorted list ? How do we do it in place ?
> *
> Sanjay Kumar
> B.Tech Final Year
> Department of Computer Engineering
> National Institute of Technology Kurukshetra
> Kurukshetra - 136119
> Haryana, India
> Contact: +91-8053566286
> *
>
> On Wed, Jan 11, 2012 at 12:34 AM, Sanjay Rajpal <sanjay.raj...@live.in>wrote:
>
>
>
>
>
>
>
> > How can it be mn log mn ?
>
> > it will be O(mn) as we elements are sorted, we simply pick minimum at each
> > iteration of the loop. Since there are mn elements, so complexity will be
> > O(mn).
>
> > Correct me if m wrong.
>
> > *
> > Sanjay Kumar
> > B.Tech Final Year
> > Department of Computer Engineering
> > National Institute of Technology Kurukshetra
> > Kurukshetra - 136119
> > Haryana, India
> > Contact: +91-8053566286
> > *
>
> > On Wed, Jan 11, 2012 at 12:29 AM, Ankur Garg <ankurga...@gmail.com> wrote:
>
> >> If we use K merge I think the time complexity would be nm lognm
>
> >> I think we must try doing in O(m*n)
>
> >> On Wed, Jan 11, 2012 at 1:54 PM, Ankur Garg <ankurga...@gmail.com> wrote:
>
> >>> @Shady Rows are already sorted ...
>
> >>> On Wed, Jan 11, 2012 at 1:53 PM, shady <sinv...@gmail.com> wrote:
>
> >>>> ^^ true, sort the rows and then a K-way merge.
>
> >>>> On Wed, Jan 11, 2012 at 1:00 PM, Sanjay Rajpal
> >>>> <sanjay.raj...@live.in>wrote:
>
> >>>>> I guess sort the array such that elements are sorted finally in such a
> >>>>> way that if we print them row by row, the result is a sorted array.
>
> >>>>> K-way merge can be useful.
> >>>>> *
> >>>>> Sanjay Kumar
> >>>>> B.Tech Final Year
> >>>>> Department of Computer Engineering
> >>>>> National Institute of Technology Kurukshetra
> >>>>> Kurukshetra - 136119
> >>>>> Haryana, India
> >>>>> Contact: +91-8053566286
> >>>>> *
>
> >>>>> On Tue, Jan 10, 2012 at 11:28 PM, prakash y
> >>>>> <yprakash....@gmail.com>wrote:
>
> >>>>>> "sort the whole matrix in ascending array" means?
> >>>>>> can you please explain ?
>
> >>>>>> On Wed, Jan 11, 2012 at 12:53 PM, atul anand <atul.87fri...@gmail.com
> >>>>>> > wrote:
>
> >>>>>>> Given 2D array.
>
> >>>>>>> The rows are sorted in ascending order and the colums are sorted in
> >>>>>>> ascending order.
>
> >>>>>>> We have to sort the whole matrix in ascending array.
>
> >>>>>>> We cannot use extra space.
>
> >>>>>>> --
> >>>>>>> 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.
>
> >> --
> >> 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.
