Posted by Traxx on Thursday, October 21, 2010 at 9:05am.
To make sure we are on the same wavelength, to me it is implicit that
1. the matrix entries are numeric
2. the insertion will preserve the given order horizontally and vertically,
3. location of non existent elements are unpredictable, and
4. The insertion of an element in a row involves shifting of elements, which in turn will disrupt the order of the elements in the columns. This has to be addressed (in mxn time!)
Do you have any suggestions?
INSERT(Y; k)
DECREASE-KEY(Y; m; n; k)
DECREASE-KEY(Y; i; j; k)
if Y [i; j] · k
then return error
Y [i; j]Ãk
thresholdÃ1
largestiÃi
largestjÃj
while(i > 1 or j > 1) and Y [i; j] < threshold
do exchangeY [i; j] $ Y [largesti; largestj ]
iÃlargesti
jÃlargestj
if i ¡ 1 ¸ 1 and Y [i; j] < Y [i ¡ 1; j]
then largestiÃi ¡ 1
largestjÃj
if j ¡ 1 ¸ 1 and Y [largesti; largestj ] < Y [i; j ¡ 1]
then largestiÃi
largestjÃj ¡ 1
thresholdÃY [largesti; largestj ]
Is this method help?
Obviously in your algorithm, some of the > and ≥ signs have not been coded properly for HTML.
This is a one-pass algorithm that does the work in O(m+n) BUT it does not guarantee the integrity of the tableau, namely after any exchange, there is no guarantee that both elements satisfy the criteria in both directions (see #4 above).
If that's what your teacher accepts, that's OK.
Example:
1 3 4 X
4 5 9 X
X X X 2
1 3 4 X
4 5 9 2
X X X X
1 3 4 X
4 5 2 9
X X X X
1 3 2 X
4 5 4 9
X X X X
1 2 3 X
4 5 4 9
X X X X
Note that row two violates the Young Tableau criteria.