[C] Una matrice può essere ordinata solo trasformandola in un array

[array96]

Volevo mettere gli elementi di una matrice in ordine crescente. Per farlo ho trasferito tutti gli elementi in un array monodimensional e usato un normale bubblesort per ordinarli. Era l'unico modo? Non esiste un metodo per ordinare gli elementi di una matrice in ordine crescente senza trasferirli in un array?

[Smoke666]

Bastava modificare bubbleSort in modo che ordinasse direttamente la matrice anzichè l'array. Non è nulla di estremamente complesso...Ma già che hai utilizzato la tecnica dell'array, perchè non ordini con il quick sort?

[array96]

Originariamente inviato da Smoke666
Bastava modificare bubbleSort in modo che ordinasse direttamente la matrice anzichè l'array. Non è nulla di estremamente complesso...Ma già che hai utilizzato la tecnica dell'array, perchè non ordini con il quick sort?

Buona idea il quick sort. Ma se non avessi voluto usare l'array, come avrei dovuto applicare bubbleSort alla matrice?

[MItaly]

Se per matrice intendi una "vera" matrice C (e non il potenziale "jagged array" fatto con un vettore monodimensionale di puntatori a vettori), il problema non si pone, dato che lo standard garantisce che gli elementi di una matrice sono memorizzati in maniera contigua, per cui con un cast puoi "vedere" la matrice bidimensionale come matrice monodimensionale e ordinarla con un normale algoritmo di ordinamento.

In caso contrario (o nel caso in cui non ti vada bene che l'ordinamento sia per righe) puoi "linearizzare" la tua matrice scrivendo una funzione che converta l'indice lineare nelle due coordinate della tua matrice.
Supponendo ad esempio che tu abbia una matrice bidimensionale che vuoi ordinare per colonne potresti scrivere una funzione del tipo:

int * elemento(size_t idx)
{
    return &matrice[idx%lunghezza][idx/lunghezza];
}

dove idx è l'"indice linearizzato", matrice è la matrice a cui accedere e lunghezza è la lunghezza di ogni riga; nell'algoritmo di ordinamento puoi quindi accedere agli elementi usando la funzione elemento invece di lavorare direttamente sull'array.

[Scara95]

Il modo più semplice te l'ho già spiegato qui, non è l'unico, ma è il più semplice...
Puoi anche implementare un Bubble Sort gestendo gli indici della matrice...
In ogni caso non serve copiare gli elementi per ordinarla, ti ho fatto un'esempio completo e provvisto di codice nell'altro thread.

[array96]

Originariamente inviato da MItaly
Se per matrice intendi una "vera" matrice C (e non il potenziale "jagged array" fatto con un vettore monodimensionale di puntatori a vettori), il problema non si pone, dato che lo standard garantisce che gli elementi di una matrice sono memorizzati in maniera contigua, per cui con un cast puoi "vedere" la matrice bidimensionale come matrice monodimensionale e ordinarla con un normale algoritmo di ordinamento.

In caso contrario (o nel caso in cui non ti vada bene che l'ordinamento sia per righe) puoi "linearizzare" la tua matrice scrivendo una funzione che converta l'indice lineare nelle due coordinate della tua matrice.
Supponendo ad esempio che tu abbia una matrice bidimensionale che vuoi ordinare per colonne potresti scrivere una funzione del tipo:

int * elemento(size_t idx)
{
    return &matrice[idx%lunghezza][idx/lunghezza];
}

dove idx è l'"indice linearizzato", matrice è la matrice a cui accedere e lunghezza è la lunghezza di ogni riga; nell'algoritmo di ordinamento puoi quindi accedere agli elementi usando la funzione elemento invece di lavorare direttamente sull'array.

Ti ringrazione per il codice. Io però non sono arrivato ancora a quel punto e posso usare solo bubblesort. Tuttavia non riesco a usarlo sulle matrici

[MItaly]

Originariamente inviato da array96
Io però non sono arrivato ancora a quel punto e posso usare solo bubblesort.

Sempre bubblesort useresti, quello che ti sto dicendo è che il bubblesort lavora con indici "lineari", per cui tutto quello che ti serve è convertire l'indice usato dal bubblesort nei due indici della matrice quando accedi agli elementi.
In altre parole: la tua matrice lavora con gli indici di riga e di colonna, il bubblesort lavora con gli indici nei quadratini; per fare la conversione dagli uni agli altri ti basta usare una divisione intera per il numero di elementi per riga (ottenendo così l'indice di riga) e prendere il resto della divisione (ottieni l'indice di colonna), viceversa se vuoi ordinare per colonna.

      0    1    2    3    4    5
   +----+----+----+----+----+----+
 0 |  0 |  1 |  2 |  3 |  4 |  5 |
   +----+----+----+----+----+----+
 1 |  6 |  7 |  8 |  9 | 10 | 11 |
   +----+----+----+----+----+----+
 2 | 12 | 13 | 14 | 15 | 16 | 17 |
   +----+----+----+----+----+----+

Ovviamente se ti basta ordinare per riga basta fare come spiegato da scara.

[array96]

Ma se il Bubblesort degli array è

for(j=0;j<n-1; j++)
  for(i=0; i<n-1; i++)
    if(vet[i]>vet[i+1])
      {aux=vet[i]; vet[i]=vet[i+1]; vet[i+1]=aux;}

non ho ben capito come si trasformerebbe

[MItaly]

Imposta un bubblesort come se dovessi ordinare un vettore di lunghezza (n x m) (dove n e m sono le dimensioni della matrice). Ogni volta che nel bubblesort accederesti al k-esimo indice del vettore converti questo numero k nei corrispondenti indici di riga e colonna della matrice, come spiegato nel post precedente.
Ma di nuovo, se ti basta ordinare la matrice "per righe" non c'è neanche bisogno di convertire l'indice: dato che le righe della matrice in memoria sono messe una in fila all'altra, ti basta fare un cast ad int* del primo elemento della matrice per "vederla" come un vettore di lunghezza n x m e applicarci il normale bubblesort.

[Scara95]

In ogni caso ecco cosa intendeva:

#include <stdio.h>
#include <stdbool.h>

#define N 5
#define M 3

int *indexer(int [][M], int);

int main(int argc, char **argv) {
	int j, k;
	int mat[N][M];
	int *e1, *e2;
	int tmp;
	bool change;
	//inserimento dati
	printf("Inserire una matrice di %ux%u elementi:\n", N, M);
	for(j = 0; j < N; j++) {
		for(k = 0; k < M; k++) {
			scanf("%d", &mat[j][k]);
		}
	}
	while(getchar() != '\n'); //pulisce il buffer dopo la lettura con scanf
	//stampa dati
	printf("\n\n");
	for(j = 0; j < N; j++) {
		for(k = 0; k < M; k++) {
			printf("%d ", mat[j][k]);
		}
		printf("\n");
	}
	//ordinamento dati
	for(j = N*M - 1; j > 0; j--) {
		change = false;
		for(k = 0; k < j; k++) {
			e1 = indexer(mat, k);
			e2 = indexer(mat, k + 1);
			if((*e1) > (*e2)) {
				tmp = *e1;
				(*e1) = (*e2);
				(*e2) = tmp;
				change = true;
			}
		}
		if(!change) break;
	}
	//stampa dati
	printf("\n\n");
	for(j = 0; j < N; j++) {
		for(k = 0; k < M; k++) {
			printf("%d ", mat[j][k]);
		}
		printf("\n");
	}
	getchar();
}

int *indexer(int mat[][M], int index) {
	return &(mat[index/M][index%M]);
}

Il codice è pressochè uguale a quello del post precedente.