Sort 2d array so biggest elements are on the main diagonal

Question

Can you please help me with that. I have 2d array

20 30 40 1 71 5 3 60 9

After sorting it should look like this:

71 30 20 1 60 5 3 9 40

So the the biggest elements are located in main diagonal. Position of other elements do not really matter in this case.

    int temp;

    for (i = 0; i < col; i++) {
        for (j = i; j < row; j++) {
            for (k = 0; k < col; k++) {
                if (m[j][k] > m[i][i]) {
                    temp = m[i][i];
                    m[i][i] = m[j][k];
                    m[j][k] = temp;
                }
            }
        }
    }

And it works for some cases, but for others fails, for example for this one

int m[5][5] = { {71, 80, 40, 200, 600}, {1, 601, 5, 3, 45}, {3, 8, 9, 81, 123}, {432, 4, 2, 321, -543}, {7, 20, 30, 5, -5} };

Thank you.

Answer 1

The problem is with the compare loops. The code find the maximum for [0.0], and then it should look for the next highest value to put in [1,1].

• The search for the 2nd maximum should exclude only the [0,0], otherwise the maximum will move to [1,1].
• Current code exclude all data in row [0].

To generalize, the search for the (i+1)-th maximum, to be placed into [i, i] should

• Exclude the diagonal elements [j, j] for j=0 .. i-1.
• Current code exclude all data in rows [0..i-1], not just the diagonal.

In code:

#include <stdio.h>

int m[5][5] = { {71, 80, 40, 200, 600}, {1, 601, 5, 3, 45}, {3, 8, 9, 81, 123}, {432, 4, 2, 321, -543}, {7, 20, 30, 5, -5} };

void main(void)
{
        int row = sizeof(m)/sizeof(m[0]) ;
        int col = row ;

    for (int i = 0; i < col; i++) {
// BAD        for (int j = i; j < row; j++) {
// Allow finding maximum in previous rows
        for (int j = 0; j < row; j++) {
            for (int k = 0; k < col; k++) {
// BAD                if ( m[j][k] > m[i][i]) {
// Replace with exclude diagonals for previous rows
                if ((j != k || j>i) && m[j][k] > m[i][i]) {
                    int temp = m[i][i];
                    m[i][i] = m[j][k];
                    m[j][k] = temp;
                }
            }
        }
    }
    for (int i = 0 ;  i<row ; i++ ) {
        for (int j=0 ; j<col ; j++ ) {
                printf (" %4d", m[i][j]) ;
        }
            printf("\n") ;
    }
}

Output:

  601   -5    9   40   71
    1  600    5    3   45
    3    8  432   80   81
  123    4    2  321 -543
    7   20   30    5  200

Answer 2

I am sure there are several approaches to solve the task.

I can suggest the following approach.

You need to write two functions. The first one finds the maximum element in a one-dimensional sub-array (the two-dimensional array is interpreted as a one-dimensional array). The second one swaps two elements of the two-dimensional array.

So at first you will fill the first row of the two-dimensional array with maximum values. And then you will swap the elements of the first row with the elements of the main diagonal.

Here is a demonstrative program.

#include <stdio.h>

size_t max_element( const int *a, size_t n )
{
    size_t max = 0;

    for ( size_t i = 1; i < n; i++ )
    { 
        if ( a[max] < a[i] ) max = i;
    }

    return max;
}

void swap( int *a, int *b )
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main(void) 
{
    enum { N = 5 };
    int a[N][N] =
    {
        {  71,  80,  40, 200,  600 }, 
        {   1, 601,   5,   3,   45 }, 
        {   3,   8,   9,  81,  123 }, 
        { 432,   4,   2, 321, -543 }, 
        {   7,  20,  30,   5,   -5 }
    };

    for ( size_t i = 0; i < N; i++ )
    {
        for ( size_t j = 0; j < N; j++ )
        {
            printf( "%4d ", a[i][j] );
        }

        putchar( '\n' );
    }

    putchar( '\n' );

    for ( size_t i = 0; i < N; i++ )
    {
        size_t max = max_element( ( const int * )a + i, N * N - i );
        swap( &a[0][i], ( int * )a + max + i );
    }

    for ( size_t i = 1; i < N; i++ ) swap( &a[0][i], &a[i][i] );

    for ( size_t i = 0; i < N; i++ )
    {
        for ( size_t j = 0; j < N; j++ )
        {
            printf( "%4d ", a[i][j] );
        }

        putchar( '\n' );
    }

    return 0;
}

Its output is

  71   80   40  200  600 
   1  601    5    3   45 
   3    8    9   81  123 
 432    4    2  321 -543 
   7   20   30    5   -5 

 601   71    9   80   -5 
   1  600    5    3   45 
   3    8  432   81  123 
  40    4    2  321 -543 
   7   20   30    5  200