Given a two-dimensional array T of size NxN, filled with various natural numbers (They do not have to be sorted in any way as in the example below.). My task is to write a program that transforms the array in such a way that all elements lying above the main diagonal are larger than each element lying on the diagonal and all elements lying below the main diagonal are to be smaller than each element on the diagonal.

For example: T looks like this:
[2,3,5]
[7,11,13]
[17,19,23]
and one of the possible solutions is:
[13,19,23]
[3,7,17]
[5,2,11]

I have no clue how to do this. Would anyone have an idea what algorithm should be used here?

CodePudding user response：

• Let's say the matrix is NxN.
• Put all N² values inside an array.
• Sort the array with whatever method you prefer (ascending order).
• In your final array, the (N²-N)/2 first values go below the diagonal, the following N values go to the diagonal, and the final (N²-N)/2 values go above the diagonal.

The following pseudo-code should do the job:

mat <- array[N][N] // To be initialized.
vec <- array[N*N]
for i : 0 to (N-1)
  for j : 0 to (N-1)
    vec[i*N j]=mat[i][j]
  next j
next i
sort(vec)
p_below <- 0
p_diag <- (N*N-N)/2
p_above <- (N*N N)/2

for i : 0 to (N-1)
  for j : 0 to (N-1)
    if (i>j)
      mat[i][j] = vec[p_above]
      p_above <- p_above   1
    endif
    if (i<j)
      mat[i][j] = vec[p_below]
      p_below <- p_below   1
    endif
    if (i=j)
      mat[i][j] = vec[p_diag]
      p_diag <- p_diag   1
    endif
  next j
next i

Code can be heavily optimized by sorting directly the matrix, using a (quite complex) custom sort operator, so it can be sorted "in place". Technically, you'll do a bijection between the matrix indices to a partitioned set of indices representing "below diagonal", "diagonal" and "above diagonal" indices.

But I'm unsure that it can be considered as an algorithm in itself, because it will be highly dependent on the language used AND on how you stored, internally, your matrix (and how iterators/indices are used). I could write one in C , but I lack knownledge to give you such an operator in Python.

Obviously, if you can't use a standard sorting function (because it can't work on anything else but an array), then you can write your own with the tricky comparison builtin the algorithm.

For such small matrixes, even a bubble-sort can work properly, but obviously implementing at least a quicksort would be better.

Elements about optimizing:

First, we speak about the trivial bijection from matrix coordinate [x][y] to [i]: i=x y*N. The invert is obviously x=floor(i/N) & y=i mod N. Then, you can parse the matrix as a vector. This is already what I do in the first part initializing vec, BTW.

With matrix coordinates, it's easy:

• Diagonal is all cells where x=y.
• The "below" partition is everywhere x<y.
• The "above" partition is everywhere x>y.

Look at coordinates in the below 3x3 matrix, it's quite evident when you know it.

0,0  1,0  2,0
0,1  1,1  2,1
0,2  1,2  2,2

We already know that the ordered vector will be composed of three parts: first the "below" partition, then the "diagonal" partition, then the "above" partition.

The next bijection is way more tricky, since it requires either a piecewise linear function OR a look-up table. The first requires no additional memory but will use more CPU power, the second use as much memory as the matrix but will require less CPU power. As always, optimization for speed often cost memory. If memory is scarse because you use huge matrixes, then you'll prefer a function.

In order to shorten a bit, I'll explain only for "below" partition. In the vector, the (N-1) first elements will be the ones belonging to the first column. Then, we'll have (N-2) elements for the 2nd column, (N-3) for the third, until we had only 1 element for the (N-1)th column. You see the scheme, sum of the number of elements and the column (zero-based index) is always (N-1).

I won't write the function, because it's quite complex and, honestly, it won't help so much to understand. Simply know that converting from matrix indices to vector is "quite easy".

The opposite is more tricky and CPU-intensive, and it SHOULD use a (N-1) element vector to store where each column starts within the vector to GREATLY speed up the process. Thanks, this vector can also be used (from end to begin) for the "above" partition, so it won't burn too much memory.

Now, you can sort your "vector" normally, simply by chaining the two bijection together with the vector index, and you'll get a matrix cell instead. As long as the sorting algorithm is stable (that's usually the case), it will works and will sort your matrix "in place", at the expense of a lot of mathematical computing to "route" the linear indexes to matrix indexes.

Please note that, despite we speak about bijections, we need ONLY the "vector to matrix" formulas. The "matrix to vector" are important - it MUST be a bijection! - but you won't use them, since you'll sort directly the (virtual) vector from 0 to N²-1.