Newsgroup: it.comp.lang.c
Titolo: OrdinamentoMatrice

Posto un bubble sort ottimizzato per matrici di mia ideazione.
Non so se sia proprio il massimo (molto probabilmente non lo e' affatto).
Se ne potrebbe discutere sul NG ed apportare eventuali migliorie.
Ogni critica costruttiva sarebbe bene accetta.
<inizio codice>
void bubbleSortMatrix (int M[][COLONNE], int row, int column)
  {
    int r, c;
    int sentinel;
    int RowCol = row * column;
    int lastRow = row - 1;
    int lastColumn = column - 1;
    printf ("\n ORDINAMENTO CRESCENTE IN CORSO...\n");
    do // Esegui...
      {
        sentinel = 0; // Azzero sentinel
        for (r = 0; r <= row - 1; r++)
            for (c = 0; c <= column - 1; c++)
              {
                if (c != lastColumn && (M[r][c] > M[r][c+1]))
                // Se non siamo a fine riga (ultima colonna) e
                // l'elemento che precede è maggiore di quello che segue.
                  {
                    scambia (M, r, r, c, c+1); // Eseguo lo scambio...
                    sentinel = 1;              // ... e segno l'evento
                  }
                else if (r != lastRow && (M[r][lastColumn] > M[r+1][0]))
                // Se non siamo all'ultima riga e l'ultimo elemento
                // della riga è maggiore del primo elemento della
                // riga successiva.
                  {
                    scambia (M, r, r+1, lastColumn, 0); // Scambio...
                    sentinel = 1;                       // ... e segno
                  }
              }
      }
    while (sentinel); // ... fino a che avvengono scambi.
    printf (" ORDINAMENTO COMPLETATO.\n\n");
  }
void scambia (int M[][COLONNE], int r1, int r2, int c1, int c2)
{
    int temp;
    temp = M[r1][c1];
    M[r1][c1] = M[r2][c2];
    M[r2][c2] = temp;
  }
<fine codice>
Marcello

Inizialmente volevo fare un paio di appunti sulle ottimizzazioni che
potresti fare... Ma poi ho deciso che non ne valeva la pena...
Dunque... Ho bevuto troppa birra, quindi non sono riuscito a capire bene
cosa vorresti fare (credo tu voglia riordinare tutti gli elementi di una
matrice quadrata per ordine, in maniera che tutti gli elementi della prima
riga siano inferiori a tutti gli elementi della seconda riga e che,
all'interno di ogni riga, la riga stessa sia ordinata)
Adesso ti dirņ un trucco che vale per molti C (forse tutti).
Quando tu fai
int a[max_righe][max_colonne]
e poi fai una
int x = a[riga][colonna] lui trasforma questo riferimento in:
int x = *(&a + riga * max_colonne + colonna)
(se osservi la formula, capisci perchč tu alla funzione scambia devi dire
quante colonne ha la tua matrice, ma non quante righe. max_righe infatti non
serve a nulla, se non a fare un controllo di non sforamento che tanto il c
non fa :-) )
Questo cosa significa? Beh... Non vorrai che ti dica tutto io :-)
Cmq il punto č che pui interpretare una matrice a due dimensioni di m righe
per n colonne come una singola matrice di m*n righe, e quindi puoi usare la
funzione qsort! :-)
--- bye

Credo di non essere stato troppo gentile nel precedente messaggio...
L'atteggiamento un po' strafottente mi viene quando bevo... Scusa :-)
(la funzione qsort serve per riordinare... E' molto veloce ed usa
l'algoritmo quick sort. Tecnicamente potresti realizzare a mano una versione
più veloce (perchè la f. qsort si collega a una funzione definita
dall'utente invece che fare una comparazione inline) ma in pratica se tu la
realizzassi a mano, probabilmente faresti peggio (nella qsort del visual c++
stanno attenti a quello che fanno... Teoricamente è ottimizzata per
un'architettura standard Intel... Se tu la leggi capisci. Non fanno cose del
tipo array[elemento], perchè sarebbe una moltiplicazione (array[elemento] è
come dire *((char*)&array[0]+sizeof(array[0]) * elemento) o qualcosa del
genere... Vedi la moltiplicazione?). Invece si tengono dei puntatori che
fanno avanzare con delle somme)
--- bye

Vedi che ho bevuto? Mi confondevo con il bsearch... Con il qsort fanno cose
più strane ancora :-) (e usano anche il goto :-) )
Pensa che al suo interno può anche decidere di usare un altro algoritmo (il
sort a inserimento) se l'array è molto piccolo.
--- bye

 funzione qsort! :-)
Non vale la pena di perdere tempo con alternative casalinghe eh? ;)
Marcello

 L'atteggiamento un po' strafottente mi viene quando bevo... Scusa :-)
Di nulla.
Non mi e' sembrato che tu sia stato scortese. ;)
Ciao.
Marcello

 Non vale la pena di perdere tempo con alternative casalinghe eh? ;)
Se è per imparare sì, se è in un ambiente produttivo no!
(imparare come funzionano i vari algoritmi di sort e quali
vantaggi/svantaggi hanno va sempre bene... Non tutti gli algoritmi di sort
vanno bene per tutte le strutture di dati.)
--- bye

questo è un bubble sort creato ed ottimizzato da me ordina matrici mono e
multidimensionali
che ne pensate? accetto critiche anche pesanti :-)
-SOF-
void bubble_iuz(int *punt, int n){
int i,k;
do{
for(i=k=0;i<n-1;i++) if(*(punt+i)>*(punt+i+1))
{ k=*(punt+i); *(punt+i)=*(punt+i+1); *(punt+i+1)=k; k=i+1; }
n=k;
}while(k>0);
}
-EOF-
"*punt" è il puntatore al primo elemento della matrice quindi se vet è
monodimensionale sarà &vet[0] invece se bidimensionale sarà &vet[0][0] e
così via 
"n" sono il totale degli elementi della matrice (il prodotto degli indici)
se vet[3][6] allora n=3*6
QUI SOTTO RIPORTO CODICE DI ESEMPIO
-SOF-
// Carica una matrice e la stampa ordinandola senza curarsi del
// numero di dimensionicon bubble_iuz
//
// Copyright (C) 2004  iuz 
sup...@iuz-lab.info
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
#include <stdio.h>
#define DIMX 5
#define DIMY 3
void bubble_iuz(int *punt, int n){
int i,k;
do{
for(i=k=0;i<n-1;i++) if(*(punt+i)>*(punt+i+1))
{ k=*(punt+i); *(punt+i)=*(punt+i+1); *(punt+i+1)=k; k=i+1; }
n=k;
}while(k>0);
}
int vet[DIMX][DIMY], p,n;
int main(void){
// qui si acquisiscono i dati
{
printf("\f");
while(n<DIMX){
p=0;
while(p<DIMY){
printf("\n%d-%d: ", n, p);
scanf("%d", &vet[n][p]);
p++;
}
n++;
}
}
// ordina l'array
// bubble_iuz(&nome_vettore[index][...], prodotto_di_tutti_gli_indici);
bubble_iuz(&vet[0][0], DIMX*DIMY);
// qui si stampa l'array ordinato
{
n=0;
while(n<DIMX){
p=0;
while(p<DIMY){
printf("\n%d-%d: %d", n, p, vet[n][p]);
p++;
}
n++;
}
}
printf("\n\n");
}
-EOF-
byez all
--------