@Ankur..
I will try to explain the approach with an example..
Say the given matrix (sorted row wise and column wise) is as follows:
a1 a2 a3 a4
b1 b2 b3 b4
c1 c2 c3 c4
d1 d2 d3 d4
Now, we want to sort the 2D array such that when all the rows are
aligned sequentially it should result in a sorted sequence..
i.e.
F1 F2 F3 F4
.............
................
F13 F14 F15 F16
such that F1 <= F2 <=....<= F16..
Now, let take each row at a time and ensure that that row contains all
the elements as expected in the output matrix..
Row - 1 :
M[0][0] = a1, which is at the correct place.. hence we won't touch
it..
Now our task is to pick the second smallest no. in the matrix and
place it at M[0][1]..
Currently, M[0][1] is the second smallest in Row-1, but we are not
sure whether its the second smallest in the entire matrix..
Hence, only way we can check that is to look in the submatrix (M[1][0]
-- M[3][3])
Now, as we know that in the submatrix enclosed within (M[1][0] -- M[3]
[3]) the smallest element present in this submatrix is positioned at
M[1][0], therefore we will check M[0][1] against M[1][0]..
If M[0][1] <= M[1][0],
that means M[0][1] has the second smallest element in the entire
matrix..
else
M[1][0] is the second smallest element in the entire matrix and
we will swap M[1][0] with M[0][1]..
Now, there are few things we need ensure if we end up swapping the
values:
1) After swapping M[0][1]'s new value will be smaller than its
original value, therefore the following is still valid:
M[0][1] <= M[0][2] <=M[0][3]
and also as M[0][1]'s new value was previously placed below
M[0][0], hence it is >= M[0][0] ..
that means after swapping Row-1 still mains the sorted
order...
2) Old value of M[1][0] <= M[1][1]..
Hence, the new value of M[0][1] is still <= M[1][1]..
therefore the sorted order of Column-2 is still valid...
3) Now, new value of M[1][0] >= M[0][0] as an impact of old value of
M[0][1] >= M[0][0]
Also, new value of M[1][0] <= M[1][1] as an impact of
old value of M[0][1] <= M[1][1]..
[ point 3 can be proved by the using the explanation from
points 1 &2..
4) Now the only thing that we need to ensure is that Column - 1 is in
sorted order i.e M[1][0] (new) <= M[2][0] (old)..
If the above is true that means the submatrix enclosed within
(M[1][0] -- M[3][3]) is stabalized and has the row/column wise sorted
order property in place...
What if its not ?? then we need to readjust the submatrix ...
Once we do that we are done for the current iteration..
[ we will talk abt stabalization in sometime.. lets take it for
granted right now..]
Now, we will follow the same approach for M[0][2], so that it holds
the third largest element..
Once we are done with Row -1.. we have the first 4 smallest elements
in place and we move on to the next row and follow a same process..
For ex-
Row -2
M[1][0] is already in place and has the 5th largest element..
Hence, lets look at M[1][1].. For this we will consider the submatrix
at (M[2][0] -- M[3][3]) and follow the same steps as
above..
-------------------------------------------------------------------------------------------------------------------
Now lets talk abt how to stabilize the submatrix when the top-left
corner of the submatrix is replaced with another value...
Say the given matrix 'R' to be stabilized is:
a b c
d e f
g h i
Now. if 'a' replaced with 'x'...
x b c
d e f
g h i
while(1)
{
If x <= min (b,d ), // here b is nothing but the element placed next
to 'x' on the same row..
// d is the element placed right below 'x'
in the same column...
then we are done...
break;
else
swap ('x', min (b,d))
}
Once, we break out of the while loop, we know that the matrix has been
stabilized and also R[0][0] has the smallest value..
// Observe that either 'x' shifts to the right position or to the
position just below it..
// Hence, whats the max. no. of shifts that 'x' can have.??
// no. of columns + no. of rows...
// Hence, heapifying time is (no. of columns + no. of rows)
Additional explanation:
Now, for matrix R[0][0], its childs when interpreted as a heap are
located at R[0][1] and R[1][0]...
Now, we know for sure that, the submatrix (R[0][1]... R[M][N]) has the
smallest element at R[0][1]..
Similarly, submatrix (R[1][0]... R[M][N]) has the smallest element at
R[1][0]...
If you observe closely then:
Elements in submatrix (R[0][0]... R[M][N])
=
Elements in submatrix (R[0][1]... R[M][N])
U
Elements in submatrix (R[1][0]... R[M][N])
U
R[0][0]..
Looking at the above equation we can say that, if R[0][0] has been
replaced and not the smallest element, then the smallest element will
be one of (R[1][0] or R[0][1] )..
And this rule applies as we keep reducing the size of the matrix.. if
shifts occur as explained above....
--------------------------------------------------------
On Jan 11, 6:10 pm, Gene <gene.ress...@gmail.com> wrote:
> Think about the cost of picking the minimum. It's not O(1).
>
> On Jan 11, 3: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.
