Ordinamento Matrice in ordine Decrescente secondo la Somma delle Righe

[Ballerina96]

Buon pomeriggio a tutti e buona domenica,
volevo chiedere il vostro aiuto per l'implementazione di una funzione che mi permetta di ordinare una matrice in modo decrescente, mettendo in prima posizione la riga con la somma maggiore e così via. Avevo pensato di modificare il selectionsort inserendo un altro controllo, ma non riesco a capire come fare.

La mia matrice è la seguente:

10 11 12 20
20 25 24 30
12 10 33 41

Inoltre, questa è la mia funzione per le somme degli elementi di ogni riga:

int somma(int mat[][COL], int r)
{
int sum=0;
int i=0;
for(i=0; i {
sum+=mat[r];
}
cout<<"La somma degli elementi sulla riga "< return sum;
};

Grazie a chi risponderà.

[Raptorista1]

Devi implementare un algoritmo di ordinamento ordinario sull'insieme delle righe, specificando che cosa significa in questo caso che una riga è maggiore o minore di un'altra.

[Super Squirrel]

Se ti può essere utile ti posto un programma fatto tempo fa. Esso ti permette di inserire una matrice di rig righe e col colonne.
Durante l'inserimento un vettore di rig elementi viene riempito in modo che l 'i-esimo elemento sia pari alla somma degli elementi dell' i-esima riga della matrice. Quindi utilizzando un generico algoritmo di ordinamento sul vettore, basta che quando si scambiano di posto gli elementi del vettore scambi di posto anche gli elementi delle righe associate attraverso un semplice ciclo for che tenga conto del numero di colonne della matrice.

#include <iostream>

using namespace std;

void scambia(int &a, int &b)
{
    int c;
    c = a;
    a = b;
    b = c;
}

void riempi_matrice(int v[100][100], int u[100], int rig, int col)
{
    for(int i = 0; i < rig; i++)
    {
        u[i] = 0;
        for(int j = 0; j < col; j++)
        {
            cout << "v[" << i + 1 << "][" << j + 1 << "] = ";
            cin >> v[i][j];
            u[i] = u[i] + v[i][j];
        }
    }
}

void mostra_matrice(int v[100][100], int rig, int col)
{
    cout << endl;
    for(int i = 0; i < rig; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cout << v[i][j] << "\t";
        }
        cout << endl;
    }
}

void ordina_matrice(int v[100][100], int u[100], int rig, int col)
{
    bool x;
    for(int k = 0; k < rig - 1; k++)
    {
        x = 0;
        for(int i = 0; i < rig - 1 - k; i++)
        {
            if(u[i] < u[i + 1])
            {
                x = 1;
                scambia(u[i], u[i + 1]);
                for(int j = 0; j < col; j++)
                {
                    scambia(v[i][j], v[i + 1][j]);
                }
            }
        }
        if(x == 0)
        {
            break;
        }
    }
}

int main()
{
    int v[100][100], u[100], rig, col;
    cout << "RIGHE (MAX 100): ";
    cin >> rig;
    cout << "COLONNE (MAX 100): ";
    cin >> col;
    riempi_matrice(v, u, rig, col);
    mostra_matrice(v, rig, col);
    ordina_matrice(v, u, rig, col);
    mostra_matrice(v, rig, col);
}

Per ottimizzare il programma, soprattutto nel caso di matrici con molte colonne, si potrebbe riempire invece di un vettore una matrice di rig righe e 2 colonne, in cui nella prima colonna mettiamo l'indice della riga e nella seconda la somma degli elementi della riga. Effettuiamo l'ordinamento delle righe della matrice rigx2 in base alle somme presenti nella seconda colonna e quindi attraverso gli indici presenti nella prima colonna sapremo quale dovrà essere l'ordine delle righe della matrice iniziale.

[vict85]

La creazione della funzione di ordinamento non sarebbe a rigore necessaria. Infatti la libreria standard del C fornisce la funzione qsort in stdlib. Se stai usando il C++ puoi usare std::sort che su alcuni compilatori usa uno smoothsort (anche se in questo caso è possibile che sia meglio usare stable_sort).

Una soluzione inefficiente del tuo problema risulta piuttosto rapida da scrivere usando qsort:

#include <stdio.h>
#include <stdlib.h>

#define ROW 3
#define COL 4

void showMat( int A[ROW][COL] );
int comp( void const *A, void const *B );

int main( void )
{
    int Mat[ROW][COL] = {{10, 11, 12, 20}, {20, 25, 24, 30}, {12, 10, 33, 41}};
    showMat( Mat );
    qsort( Mat, ROW, COL * sizeof( int ), comp );
    puts( "" );
    showMat( Mat );
}

void showMat( int A[ROW][COL] )
{
    for ( int i = 0; i != ROW; ++i ) {
        for ( int j = 0; j != COL; ++j ) {
            printf( "%d ", A[i][j] );
        }
        puts( "" );
    }
}

int comp( void const *A, void const *B )
{
    int const *rA = ( int const * ) A;
    int const *rB = ( int const * ) B;
    int somma = 0;
    for ( int i = 0; i != COL; ++i ) {
        somma += ( rA[i] - rB[i] );
    }
    return somma;
}

anche se non è esattamente un approccio da neofiti in quanto ha a che fare con puntatori a funzioni. Nota inoltre che le cose si complicano parecchio se COL non è fissato in tempo di compilazione.

L'ottimizzazione richiede di fare qualche lavoro aggiuntivo non esattamente banale. Probabilmente non richiesta dal professore. E' comunque un esercizio che vale la pena provare a fare una volta che hai un po' di dimestichezza con il sistema.

P.S.: In C++ le cose si fanno più divertenti perché si può usare una lambda per il confronto e "catturare" nella lambda l'array con le somme precalcolate. D'altra parte se COL non è fissato a tempo di compilazione questo gioco di fa più macchinoso (a meno di usare GCC e le sue estensioni).