Sorry I did not realize you meant the anti-diagonal. Dave gave a good
example where the anti-diagonal also does not contain the median.
If you go back to the partitions I described, you can "force" the
median to be any element that appears just right or below a partition
with 1+floor(N^2) elements <=P by adjusting values >= P.
The partition line for 91 in Dave's example is 54 53 52 21 31 41 91.
This encloses 13 elements = 1+floor(25/2). For example to move the
median to 112 (to the right of 21 and below 52), just increase 91 to
113.
I still think binary search using partition lines as left and right
brackets is the best solution.
On Nov 6, 5:52 am, Robert Badita <robert.bad...@gmail.com> wrote:
> It's the wrong diagonal and that algo still holds until another example. btw
> I think if the median of the sorted matrix is the median of the second
> diagonal then you have found a stable algorithm to find the median of any
> array by sorting rows and columns in O(2 sqrt N * sqrt N * log sqrt N) = O(N
> log N) then apply the solution recursively on sqrt N elements. It is no
> better though than the unstable O(N) method of qsort 1 branch.
>
> On Nov 5, 2011, at 23:32, Gene <gene.ress...@gmail.com> wrote:
>
>
>
> > Unfortunately this isn't true. See the example I gave earlier:
>
> > 1 2 3
> > 2 4 5
> > 3 4 6
>
> > Thje median is 3.
>
> > 1 2 2 3 >3< 4 4 5 6
>
> > Niether one of the 3's lies on the diagonal.
>
> > When you pick any element P on the diagonal, all you know is that
> > anything to the right and downward is no less than P and everything to
> > the left and upward is no greater. This leaves the upper right and
> > lower left rectangles of the matrix unrelated to P.
>
> > On Nov 5, 3:51 am, ankit agarwal <ankit.agarwal.n...@gmail.com> wrote:
> >> Hi,
>
> >> I think the median will always lie on the diagonal
> >> a[n][1] ---- a[1][n]
> >> because the elements on the LHS making the upper triangle will
> >> always be less than or equal to the elements on the diagonal
> >> and the RHS, elements in the lower triangle will be greater than or
> >> equal to them.
>
> >> so sort the diagonal and find the middle element, that will be the
> >> median.
>
> >> Thanks
> >> Ankit Agarwal
>
> >> On Nov 5, 1:29 am, Gene <gene.ress...@gmail.com> wrote:
>
> >>> Here's an idea. Say we pick any element P in the 2D array A and use
> >>> it to fill in an N element array X as follows.
>
> >>> j = N;
> >>> for i = 1 to N do
> >>> while A(i, j) > P do
> >>> j = j - 1;
> >>> end;
> >>> X(i) = j;
> >>> end;
>
> >>> This algorithm needs O(N) time.
>
> >>> The elements of X split each row with respect to P. That is, for each
> >>> i = 1 to N,
>
> >>> A(i, j) <= P if 0 < j <= X(i), A(i,j) > P if X(i) < j <= N.
>
> >>> Now the strategy is to create two length N arrays a = [0,0,...0]; and
> >>> b = [N,N,...]. We'll maintain the invariant that a[i] < Median <= b[i]
> >>> for some i. I.e, they "bracket" the median.
>
> >>> We define functions L(a) = sum_i( a(i) ) and R(b) = sum_i( N -
> >>> b(i) ). These tell us how many elements there are left and right of
> >>> the bracket.
>
> >>> Now reduce the bracket as in binary search: Guess a value P, compute
> >>> X. If L(X) >= R(X), set b = X else set a = X.
>
> >>> Keep guessing new P values in a way that ensures we reduce the number
> >>> of elements between a and b by some fixed fraction. If we can do
> >>> that, we'll get to 1 element in O(N log N) time.
>
> >>> The remaining problem is picking good P's. Certainly the first time is
> >>> easy. Just take A(N/2, N/2). This has approximately (at least) N^2/4
> >>> elements larger than it and N^2/4 smaller due to the sorted rows and
> >>> columns. This is what we need to get O(N log N) performance.
>
> >>> But after the first split, things get trickier. The area between a and
> >>> b takes on the shape of a slash / /, so you can't just pick a P that
> >>> moves a and b together by a fixed fraction of remaining elements.
>
> >>> Not to worry! You can quickly look up the (at most) N row medians in
> >>> the bracket, i.e.
>
> >>> { A(i, (a[i] + b[i] + 1) / 2) | a[i]<b[i] , i = 1 to N }
>
> >>> and use the well known O(N) median selection algorithm to get a median
> >>> of this. This has the quality we want of being somewhere roughly in
> >>> the middle half of the remaining elements. The logic is the same as
> >>> the selection algorithm itself, but in our case the rows are pre-
> >>> sorted.
>
> >>> In all, each partitioning step requires O(N), and a fixed fraction
> >>> (about 1/2) of the elements will be eliminated from the bracket with
> >>> each step. Thus O(log n) steps will be needed to bring the bracket to
> >>> size 1 for an overall cost of O(N log N).
>
> >>> I don't doubt that there's a simpler way, but this one seems to work.
> >>> Anyone see problems?
>
> >>> On Nov 3, 3:41 pm, sravanreddy001 <sravanreddy...@gmail.com> wrote:
>
> >>>> any better solution than O(N^2) in worst case?
> >>>> How do we take advantage of sorting and find in O(N lg N)- Hide quoted
> >>>> text -
>
> >> - Show quoted text -
>
> > --
> > 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
> > athttp://groups.google.com/group/algogeeks?hl=en.
On Nov 6, 4:11 am, mohit verma <mohit89m...@gmail.com> wrote:
> @Gene
> As i said in my earlier post right to left diagonal partitions the martix
> into 2 equal number of elements. So now the median must be in this
> diagonal. Now our focus is on finding median of this diagonal only.
> I think this works fine. Can u give some test case for which it fails?
>
>
>
>
>
> On Sun, Nov 6, 2011 at 3:02 AM, Gene <gene.ress...@gmail.com> wrote:
> > Unfortunately this isn't true. See the example I gave earlier:
>
> > 1 2 3
> > 2 4 5
> > 3 4 6
>
> > Thje median is 3.
>
> > 1 2 2 3 >3< 4 4 5 6
>
> > Niether one of the 3's lies on the diagonal.
>
> > When you pick any element P on the diagonal, all you know is that
> > anything to the right and downward is no less than P and everything to
> > the left and upward is no greater. This leaves the upper right and
> > lower left rectangles of the matrix unrelated to P.
>
> > On Nov 5, 3:51 am, ankit agarwal <ankit.agarwal.n...@gmail.com> wrote:
> > > Hi,
>
> > > I think the median will always lie on the diagonal
> > > a[n][1] ---- a[1][n]
> > > because the elements on the LHS making the upper triangle will
> > > always be less than or equal to the elements on the diagonal
> > > and the RHS, elements in the lower triangle will be greater than or
> > > equal to them.
>
> > > so sort the diagonal and find the middle element, that will be the
> > > median.
>
> > > Thanks
> > > Ankit Agarwal
>
> > > On Nov 5, 1:29 am, Gene <gene.ress...@gmail.com> wrote:
>
> > > > Here's an idea. Say we pick any element P in the 2D array A and use
> > > > it to fill in an N element array X as follows.
>
> > > > j = N;
> > > > for i = 1 to N do
> > > > while A(i, j) > P do
> > > > j = j - 1;
> > > > end;
> > > > X(i) = j;
> > > > end;
>
> > > > This algorithm needs O(N) time.
>
> > > > The elements of X split each row with respect to P. That is, for each
> > > > i = 1 to N,
>
> > > > A(i, j) <= P if 0 < j <= X(i), A(i,j) > P if X(i) < j <= N.
>
> > > > Now the strategy is to create two length N arrays a = [0,0,...0]; and
> > > > b = [N,N,...]. We'll maintain the invariant that a[i] < Median <= b[i]
> > > > for some i. I.e, they "bracket" the median.
>
> > > > We define functions L(a) = sum_i( a(i) ) and R(b) = sum_i( N -
> > > > b(i) ). These tell us how many elements there are left and right of
> > > > the bracket.
>
> > > > Now reduce the bracket as in binary search: Guess a value P, compute
> > > > X. If L(X) >= R(X), set b = X else set a = X.
>
> > > > Keep guessing new P values in a way that ensures we reduce the number
> > > > of elements between a and b by some fixed fraction. If we can do
> > > > that, we'll get to 1 element in O(N log N) time.
>
> > > > The remaining problem is picking good P's. Certainly the first time is
> > > > easy. Just take A(N/2, N/2). This has approximately (at least) N^2/4
> > > > elements larger than it and N^2/4 smaller due to the sorted rows and
> > > > columns. This is what we need to get O(N log N) performance.
>
> > > > But after the first split, things get trickier. The area between a and
> > > > b takes on the shape of a slash / /, so you can't just pick a P that
> > > > moves a and b together by a fixed fraction of remaining elements.
>
> > > > Not to worry! You can quickly look up the (at most) N row medians in
> > > > the bracket, i.e.
>
> > > > { A(i, (a[i] + b[i] + 1) / 2) | a[i]<b[i] , i = 1 to N }
>
> > > > and use the well known O(N) median selection algorithm to get a median
> > > > of this. This has the quality we want of being somewhere roughly in
> > > > the middle half of the remaining elements. The logic is the same as
> > > > the selection algorithm itself, but in our case the rows are pre-
> > > > sorted.
>
> > > > In all, each partitioning step requires O(N), and a fixed fraction
> > > > (about 1/2) of the elements will be eliminated from the bracket with
> > > > each step. Thus O(log n) steps will be needed to bring the bracket to
> > > > size 1 for an overall cost of O(N log N).
>
> > > > I don't doubt that there's a simpler way, but this one seems to work.
> > > > Anyone see problems?
>
> > > > On Nov 3, 3:41 pm, sravanreddy001 <sravanreddy...@gmail.com> wrote:
>
> > > > > any better solution than O(N^2) in worst case?
> > > > > How do we take advantage of sorting and find in O(N lg N)- Hide
> > quoted text -
>
> > > - Show quoted text -
>
> > --
> > 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.
>
> --
> Mohit
--
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.
