Newsgroup: it.comp.lang.c
Titolo: Bubble Sort Ottimizzato

Sempre proseguendo sullo studio di alcuni algoritmi e sulla loro
efficienza/migliorabilità, ora tocca all'ottimizzazione dell'ottimizzazione
del Bubble Sort :-))
Vabbè...mi spiego :
il codice che ho buttato giù vede il bubble sort ottimizzato.... ossia
l'ordinamento a bolle "classico" con migliorate due pecche che aveva quello
"tradizionale":
1. quella di capire immediatamente se un vettore è già ordinato;
2. l'atra di non arrivare a fine vettore ad ogni passata ma bensi a n-1 con
la prima passata... ad n-2 alla seconda ...ad n-3 etc etc (n = lunghezza del
vettore).
Ora ho bisogno di aggiungere un ULTERIORE miglioramento a sto cribbio di
bubble sort già ottimizzato:
-> ossia alternare le "passate" sul vettore... prima da sinistra a
destra..... poi da destra a sinistra...
insomma alternare un loop da sn a ds con uno da ds a sn.
Posto il codice del bubble sort ottmizzato che ho provato a fare e che
"sembra" andare bene.
Mi dareste una mano a migliorarlo ulteriormente con la storia delle passate?
:-))
tenete presente che troverete un piccolo vettore all'interno della funzione
(due posizioni) perchè mi serve per tenere il conto degli scambi/confronti
effettuati... lo studio è su quelli dopo tutto.
Beh...ho annoiato pure troppo...ora spero che qualcuno mi aiuti...
<CODE>
void bubble_sort(int vett[],int dim,int risultati[])
{
   int  conta_confronti = 0, conta_scambi = 0 , booleana = 0;
   int  giri,j,appoggio;
   for(giri = 1; giri <= dim-1; giri++)
   {
    for(j = 0; j <= dim-1-giri; j++)
     {
       if(vett[j] > vett[j+1])
       {
          booleana = 1;
          appoggio  = vett[j];
          vett[j]   = vett[j+1];
          vett[j+1] = appoggio;
          conta_scambi++;
       }
       conta_confronti ++;
     }
     if(booleana != 1)
       giri = dim ;
    }
    risultati[1] = conta_scambi ;
    risultati[0] = conta_confronti;
     return;
}
</CODE>
Tanto lo so che da qualche parte su questo forum c'e' un tommy che mi
osserva! :-))
(grazie per la scorsa volta! mi hai illuminato un moooondo!! :-))
Shaden

.
Sei tu?!?
Tommy

 Tommy
No mi spiace! Mai usato un nick del genere :(
Shaden

 No mi spiace! Mai usato un nick del genere :(
Beh, allora cerca un thread su 
google.it
 gruppi che si chiama Migliorare
libreria ed e' stato su it.comp.lang.c++ in data 28/03/2003 (la mia
risposta). In fondo troverai un modo (a mio) avviso leggermente piu'
elegante per scrivere il tuo bubblesort con ottimizzazioni 1 e 2.
Piu' le spiegazioni del funzionamento dell'algoritmo e di tali
ottimizzazioni. Ti riporto il codice (scusa se e' in C++):
<CODE>
template<class T>
void bubbleSort(T a[], int size)
{
    bool is_sorted=false;
    int p=0,q=0;
    T tmp;
    while(!is_sorted){
        is_sorted=true;
        ++p;
        for(q=0;q<size-p;++q){
            if(a[q]>a[q+1]){
                tmp=a[q];
                a[q]=a[q+1];
                a[q+1]=tmp;
                is_sorted=false;
            }
        }
    }
}
</CODE>
Il ciclo interno e' molto simile. Il ciclo esterno e' ridotto ad un semplice
"fino a che non e' ordinata" che a mio avviso la rende molto piu' leggibile.
Non ti sto propendo nulla, il tuo "stile" va piu' che bene. Tuttavia, visto
che stai indagando sul bubblesort, ti volevo far vedere come lo "vedo" io.
Si traduce in poche parole di italiano:
"Fino a che non e' ordinato, fai il ciclo interno con il controllo e lo
swap. Ogni volta che fai il ciclo interno termina un elemento prima."
Questa e' la descrizione (scusa l'italiano PESSIMO), e qundi l'algoritmo
contiene un:
- while(!is_sorted)
- un ++p che si riflette in q<size-p (Ogni volta che fai il ciclo interno
termina un elemento prima)
- un ciclo interno con controllo e swap
Nulla altro! (se non un  is_sorted=true; che assume l'array sia ordinato e
se non lo e' (avviene uno swap) allora fa is_sorted=false;).
Beh, buon lavoro e se non puoi postare il codice, posta i risulati che sono
piu' interessanti del codice, anche se penso non cambi praticamente nulla!
Tommy

 Shaden
Bumulo (anch'io Tommy per l'anagrafe)
PS ti si rivede (rilegge) quando fai il mergesort??? :-))

 questa č parte dell'algoritmo di bubblesort e non č un'ottimizzazione...
Beh, capisco quello che vuoi dire. E' che molti libri riportano il
bubblesort senza questa feature. Come te, credo anche io che tale feature
faccia parte dell'algoritmo stesso e quindi non posso fare altro che darti
ragione.
Tommy

 Tommy
(Anch'io  Tommy) as Bumulo

>>1. quella di capire immediatamente se un vettore è già ordinato;
io ho sottointeso ad ogni iterazione del outer loop. Forse hai ragione tu,
intendeva solo alla prima iterazione dell'outer loop.
Ad ogni modo, cosa intendesse davvero lo sa solo Shaden.
Una cosa e' certa: io do troppe cose per scontato.... ma almeno gli avevo
detto di rileggere il messaggio che ho scritto tempo fa sul bubblesort ed in
tale messaggio dicevo:
<QUOTE>
Inoltre cosa succede se la sequenza e' gia' ordinata, oppure e' parzialmente
ordinata e dopo pochi cicli esterni gia' risulta ordinata???
....
Ecco allora che conviene introdurre un valore booleano che testa se l'array
e' ordinato o meno. Se e' ordinato smette. (ovvio questa operazione non deve
costare in termini computazioni altrimenti....)
In questo modo se bastano 3 cicli esterni per ordinare l'array, la funzione
terminera' ......
<QUOTE>
Inoltre il codice che ho riportato a Shaden ha questa feature.
Immagino Shaden debba ricalcolare "il conto degli scambi/confronti" dopo
aver corretto questo suo "errore".
Tommy

 No mi spiace! Mai usato un nick del genere :(
Ah, ho capito, sei quello della "funzione empirica" ed hai scelto il
bubblesort.... ok.
Assicurati di fare anche la modifica che ti suggerisce Bumulo e che puoi
vedere applicata nel codice postato da me in precedenza, fatta questa
modifica avrai dati certamente migliori!
Tommy


beh...credo proprio che verrà assegnato come implementazione al progetto
anche lo studio del mergesort...e temo ribiomberò qui :-PPP
...scusate la brevità ma devo scappare... giri burocratici mi
aspettano...che palle!!!
Shaden

 PS ti si rivede (rilegge) quando fai il mergesort??? :-))
Shaden
P.s. non è che conoscete dei buonissimi siti che riportano fedelmente le
analisi di complessità di questi vari algoritmi? (quindi zuppi di calcolo di
funzione asintotiche dell'algoritmo... etc etc)  :-))