correction : /*set min at position A[i+1][0] after heafiying */
On Wed, Jan 11, 2012 at 11:07 PM, atul anand <atul.87fri...@gmail.com>wrote:
> @Lucifier :
> yes i didnt hepified properly in my previous post intentionally. i only
> purpose was to set min at position A[i+1][j] after heafiying.( rest i dint
> care ) .
>
> secondly about the complexity, what i was saying
> if given array is:-
>
> 1 3 4 8 9
> 2 5 18 25 50
> 6 7 22 45 55
>
> now comparing 3 > 2 , swap we get
>
> 1 2 4 8 9
> 3 5 18 25 50
> 6 7 22 45 55
> now about heapifying the highlighted array , i was considering this
> highlighted matrix
> 3 5 18 25 50
> 6 7 22 45 55
>
> as two 1-dimensional array 3 5 18 25 50 6 7 22 45 55
>
> now we can apply heapify procedure to this 1-D array (bcozz in m/m this 2D
> array is nothing but contiguous acquired space )
>
> PARENT = floor(*i*/2)
> LEFT (*i*) = 2i
> RIGHT (*i*) = 2i + 1
>
> is this approach is wrong ??
>
>
> On Wed, Jan 11, 2012 at 10:34 PM, Lucifer <sourabhd2...@gmail.com> wrote:
>
>> @atul..
>>
>> Sorry, but i don't agree with both of ur posts...
>>
>> First of all, the complexity won't be log(m*n) for heapifying..
>> log(m*n) is valid in case of a heap represented in the form of a
>> binary tree..
>> But, i have have repeatedly stressing in my previous posts that the
>> submatrix heap is not a binary tree heap but rather a graph or say a
>> binary tree (not really tree) where its subtrees share some nodes...
>>
>> Disagree with the following comment..
>> /**
>> it seem that the sub-matrix need to be heapifyed for A[i][j] is
>> A[i+1][j] to A[row][col]
>> there is no need to include A[i][j+1] to A[i][col] for A[i][j] as you
>> have
>> mentioned above.
>> **/
>>
>> Also, i see that you have not properly heapified the submatrices
>> correctly in the example that u have provided in the previous post..
>>
>> Plz go thru my last post and see if ur doubts can get clarified..
>>
>> ---------------------------------------------
>>
>> Really sorry, in case previously given details by me were
>> inadequate...
>> Was posting in a hurry :)...
>> --------------------------------------------
>> Hope, now all doubts would be cleared...
>> -----------------------------------------------
>>
>>
>> On Jan 11, 9:55 pm, Lucifer <sourabhd2...@gmail.com> wrote:
>> > @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.
>>
>>
>
--
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.
