@correction:
/*
basically either go down or go
*right* in case adjustment is required...
*/
On Jan 11, 1:56 pm, Lucifer <sourabhd2...@gmail.com> wrote:
> @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.
