[c] ordinamento crescente righe matrice

[mikael2]

dovrei scrivere una procedura tipo merge-sort che mi ordina in modo crescente le righe di una matrice [j] nel modo più semplice possibile come si può fare?

[vict85]

Con che relazione d'ordine intenti ordinare le righe?

[mikael2]

in che senso?

[giozh]

Nel senso di cosa intendi per ordinare le righe della matrice. vuoi ordinare per ogni riga gli elementi contenuti, o vuoi "muovere" le righe (lasciandone inalterato il contenuto) secondo un qualche ordine?

[vict85]

"giozh":Nel senso di cosa intendi per ordinare le righe della matrice. vuoi ordinare per ogni riga gli elementi contenuti, o vuoi "muovere" le righe (lasciandone inalterato il contenuto) secondo un qualche ordine?

No no, io mi riferivo proprio a che ordine. Insomma, quando una riga è maggiore di un'altra?

Non penso che tu voglia ordinare ogni singola riga in modo crescente perché potresti rendere la matrice in questione assolutamente priva di senso (insomma non manterresti le colonne).

[mikael2]

dovrei ordinare gli elementi delle righe della matrice in ordine crescente(dovrei tipo modificare il merge sort), però in base al grado in uscita minore. ti allego il codice che ho fatto però non è cn il merge sort sperando che capisci perchè non so se va bene.

void ordinametoRighe3()
{
int temp,pos,i,j;
 for(i=0;i<n;i++)
 {
   for(pos=0;pos<n;pos++)
  {
     for(j=pos;j<n;j++)
     {
        if(nAdj[Adj[i][j]]<nAdj[Adj[i][pos]])
        {
            temp=nAdj[Adj[i][j]];

           nAdj[Adj[i][j]]=nAdj[Adj[i][pos]];

           nAdj[ Adj[i][pos]]=temp;  
        }    
  
    }
  }
 }
}

[vict85]

Ok, stai facendo esattamente quello che pensavo non aveva senso fare. Il codice non va bene, comunque una volta che implementi un merge sort su una riga ti basta chiamarlo e applicarlo a quella riga. Insomma una matrice viene vista come un array monodimensionale in C.

Detto questo a che ti serve?

[mikael2]

questo metodo mi serve per poi applicarlo ad una permutazione. praticamente come va scritto il codice nel modo più elementare possibile ?

[Obidream]

L'idea potrebbe essere questa:
(Puoi ignorare tranquillamente il typedef, la funzione cmp e sostituire al posto di qsort il tuo mergesort per ordinare m[j] )

#include <stdio.h>
#include <stdlib.h>
#define N 5
#define M 6

typedef int (*ptr) (const void *,const void *);

int cmp(int *a, int *b)
{
return (*a-*b);
}

int main()
{
int m[N][M];
int i,j,k;
k=30;
for(i=0;i<N;i++)
    for(j=0;j<M;j++)
        m[i][j]=k=k-1;
for(i=0;i<N;i++)
    {
    for(j=0;j<M;j++)
        printf("%2d ",m[i][j]);
    putchar('\n');
    }
for(j=0;j<M;j++)
    qsort(m[j],M,sizeof(int),(ptr)cmp);
puts("Dopo l'ordinamento:");
for(i=0;i<N;i++)
    {
    for(j=0;j<M;j++)
        printf("%2d ",m[i][j]);
    putchar('\n');
    }
return 0;
}

[mikael2]

cosa significa m][j]=k=k-1, mi puoi descrivere il fuzionamento

[vict85]

Mi continua a sfuggire il senso di tutto ciò comunque penso che siccome stai lavorando con interi, compresi tra 0 e n (se non sbaglio), allora tanto vale usare il Counting sort.

[Obidream]

"mikael":cosa significa m][j]=k=k-1, mi puoi descrivere il fuzionamento

Serviva solo a riempire la matrice con dei numeri, ma non avevo voglia di scriverne una a mano...
In sostanza decrementa k e lo assegna a m[j], ma questo esula dall'ordinamento degli elementi delle righe.

[vict85]

@ mikael : questo particolare algoritmo potrei anche scrivertelo velocemente (per esempio con il counting sort) ma continuo a pensare che non serva a nulla. Mi ricordi qual'è il tuo progetto generale.

[mikael2]

lo devo fare sul merge sort. devo ordinare gli elementi di riga dei vertici adiacenti(Adj[j]) in funzione non di quanto sono grandi ma in base al valore del grado che essi assumono(nAdj[]).Nel merge sort devo vedere quando utilizzare l'elemento e quando utilizzare il grado dell'elemento.Questo mi è stato detto di fare da un prof Come si fa?

[vict85]

Dato un insieme ordinato di vertici di un grafo orientato, il grafo di adiacenza è definito come:
\[ \mathrm{adj}_{i,j} = \begin{cases} 1 & \text{se esiste un lato che va dal vertice } i \text{al vertice } j \\ 0 & \text{altrimenti} \end{cases} \]
Il grado di entrata di un vertice è il numero di lati entranti, il grado di uscita è il numero di lati uscenti.

Ciò che tu devi ordinare però non è la matrice, ma i vertici. Riordinando i vertici la matrice di adiacenza per questo nuovo insieme ordinato di vertici sarà di una forma (probabilmente) più bella. In sostanza devi usare il merge sort su nAdj memorizzandoti la permutazione generata dal mergesort e poi applicare la permutazione sia alle righe che alle colonne della matrice.

Solo in questo modo il grado rappresentato dalla prima matrice e quello della secondo sono isomorfi (insomma sono lo stesso grafo). Non so cosa hai capito dal professore ma ritengo sia questo che ti è stato richiesto. Perché questo è ciò che ha senso fare.

[mikael2]

va bene in questo modo il merge sort come l ho modificato il prof ha detto che va bene però quando stampo adj[] gli elementi non sono ordinati in ordine crescente dove è l'errore? come va aggiustato?

void Merge(int A[], int p, int q, int r) {
  int i, j, k, B[100];

  i = p;
  j = q+1;
  k = 0;
  while (i<=q && j<=r) {
    if (nAdj[A[i]]<nAdj[A[j]]) {
      B[k] = A[i];
      i++;
    } else {
      B[k] = A[j];
      j++;
    }
    k++;
  }
  while (i<=q) {
    B[k] = A[i];
    i++;
    k++;
  }
  while (j<=r) {
    B[k] = A[j];
    j++;
    k++;
  }
  for (k=p; k<=r; k++)
    A[k] = B[k-p];
  return;
}


for(j=0;j<n;j++){

   
MergeSort(Adj[j], 0,n-1);
}