Newsgroup: it.comp.lang.c
Titolo: ordina matrici mono e multi dim

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
--------

 che ne pensate? accetto critiche anche pesanti :-)
penso che in ogni caso il bubble sort puo' andar bene solo
per ordinare vettori molto piccoli.
Per ordinare array piu' grandi e' molto meglio usare
un ordinamento come il qsort (del quale esistono svariate
implementazioni, una anche in stdlib) che puo' essere molto ma molto
piu' veloce del bubble sort.
ciao,
g.

> { k=*(punt+i); *(punt+i)=*(punt+i+1); *(punt+i+1)=k; k=i+1; }
Qui tu usi k sia come variabile per fare lo swap che come indice. Non lo
devi fare! Non è di sicuro i 4 bytes (probabili) che risparmi sullo stack ad
aumentare la velocità. Se domani decidi di trasformare il tuo bubble sort in
un programma per ordinare double ti salta tutto!
--- bye

 piu' veloce del bubble sort.
Su questo concordo: mi permetto di ricordare anche un altro algoritmo
valido, il merge sort.
Per quanto riguarda il codice le mie osservazioni sono le seguenti:
1. la leggibilità del codice non è ottima (anche se il "casino" può
essere
   avvenuto facendo il copia-incolla);
2. hai utilizzato la variabile k sia per scambiare i termini fuori
ordine sia
   come indice per la scansione: è meglio non farlo per permettere più
   semplici eventuali modifiche future del codice;
3. ottimizzare non vuol dire solo utilizzare i puntatori a tutto
spiano: dove
   è possibile accedere ad un array mediante indice/i io solitamente
non uso
   i puntatori (mi fido del compilatore, è lui che deve rendere
equivalenti le
   istruzioni "a[1] = 5;" e "*(a + 1) = 5;"
Stefano

 bubble sort e quello di quick sort sono praticamente equivalenti.
Dipende dall'algoritmo di quicksort che implementi.
Un algoritmo randomizzato non ha generalmente questi problemi,
cioe li ha con probabilita' cosi' bassa da poter essere
trascurata (anche perche' cala con l'aumentare del numero
di elementi). Al contrario il bubble sort ha con alta probabilita'
un costo alto.
In ogni caso (scusa la pignolaggine logica...) la bonta' o meno
del quicksort non inficia la mia affermazione di cui sopra sul fatto
che il bubble sort faccia quasi sempre schifo su vettori grandi.
Poi naturalmente se uno deve ordinare 7 vettori di 10 interi
puo' fare un po' come gli pare.
Scrivendo dei programmi di tipo matematico/combinatorio
mi e' capitato di dover ordinare ripetutamente array di svariati milioni
di elementi : se usavo il bubble sort ero ancora li'...
In casi estremi puo' convenire evitare la chiamata di qsort
(che ha ovviamente degli overhead) e implementarsi il proprio
qsort. Da questo punto di vista (mi duole dirlo :-)  ) il C++
va meglio perche' usando per il sort nella STL un template,
(diciamo una sorta di macro) nel caso di sorting di array di
oggetti elemetari (come gli int) va decisamente meglio del
qsort del c. Almeno sulla mia macchina.
Tutto questo va comunque valutato in funzione del programma
che uno sta scrivendo. Effettivamente se non hai esigenze
particolari di velocita' il bubble sort puo' andare bene,
anche se in quel caso io userei comunque la chiamata a qsort
perche' mi fido piu' delle librerie del C che dei programmi
che faccio io ... :-)
ciao,
g.