Bubble Sort Ottimizzato
Shaden
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
Tommy
"Shaden" <simonet...@virgilio.it.LEVATE.STO.MAIUSCOLO> wrote
> 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:
Non sono sicuro ci sia molto altro da ottimizzare ;-)
> -> 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.
Ah, carina, ma.... non credo dia grossi vantaggi... Ad ogni modo e' piu'
complicata di quanto tu possa pensare....
Il tuo punto 2), e' una buona ottimizzazione di cui ho parlato tempo fa.
Questa si basa sul principio che alla prima passata l'elemento piu' grande,
ovunque si trovi, arrivera' fino alla fine dell'array. Alla seconda passata
il secondo piu' grande e cosi' via!
Se abbiamo:
8 5 4 6
faremo lo swap di 8 e 5
5 8 4 6
poi di 8 e 4
5 4 8 6
poi di 8 e 6
5 4 6 8
ora possiamo considerare solo 5 4 6, fare lo swap dei primi 2:
4 5 6
e voila'!
Bene, guarda se pero' ci muoviamo da destra a sinistra:
8 5 4 6
facciamo lo swap di 4 e 6 se necessario.
8 5 4 6
facciamo lo swap di 5 e 4 se necessario
8 4 5 6
facciamo lo swap di 8 e 4 se necessario
4 8 5 6
Ok, come vedi l'8 non e' piu' in ultima posizione! In pratica il punto 2 non
e' piu' garantito.
Ok, potresti quindi rinunciare al tuo tentativo, ma.....
Se ci fai caso pero' questa volta garantiamo che l'elemento piu' piccolo sia
a sinitra!!!
In pratica quando ho detto (all'inzio di questa mail) "Ad ogni modo e' piu'
complicata di quanto tu possa pensare...." intendevo proprio questo. Si puo'
fare, non so quali vantaggi dia, questo me lo dirai tu, ma invece di fare:
ogni volta un elemento in meno a destra:
da 0 a 9
da 0 a 8
da 0 a 7
da 0 a 6
etc...
dovrai toglierne uno a destra quando vai da sinistra a destra ed uno a
sinistra quando vai da destra a sinistra:
da 0 a 9
da 0 a 8 (beh, da 8 a 0)
da 1 a 8
da 1 a 7 (beh, da 7 a 1)
da 2 a 7
da 2 a 6 (beh, da 6 a 2)
etc....
Il fatto che io abbia volutamente scritto ad esempio alla riga 2, da 0 a 8 e
poi un "beh, da 8 a 0" e' per non confonderti. Effettivamente sarebbe da 8 a
0 visto che ce ci muoviamo da destra a sinistra, ma gli indici da usare sono
comuque da 0 a 8. Spero di non aver creato confuzione.
Se te ne freghi di tutto questo e dai per scontato il punto 2, beh, otterrai
(a volte) array non ordinati ;-)
Fammi un piacere, sappimi poi dire se ci sono vantaggi in questo processo
"alterno"....
> 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?
> :-))
Allora, forse ti ho gia' aiutato abbastanza....
Il modo piu' leggibile per codificarlo e' usare un semplice
if(variabile_loop_esterno%2){
fai ciclo interno passata da sinistra a destra
}else{
fai ciclo interno passata da destra a sinistra
}
ricordati inoltre di avere due variabili per ricordarti quanto "mangiare" a
destra e sinistra. giri non va piu' bene (dim-1-giri).
In entrambe le versioni del for dovrai avere: da 0+fatto_a_sinistra fino a
dim-1-fatto_a_destra. In un for incrementi fatto a destra e nell'altro fatto
a sinistra. Questi vanno entrambi inizializzati a 0.
Posta il codice appena hai fatto e se hai problemi posta quello che hai
fatto che poi risolviamo. Ma vedrai che e' semplice.
> 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.
ok.
> 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!! :-))
Io avevo scritto un messaggio con la spiegazione delle ottimizzazioni 1 e 2
a "Kleidemos" <france...@tin.it>.
Sei tu?!?
Tommy
Shaden
illuminante. :-)) Spero che postando il codice non lo rubi qualcuno che sta
in corso di laurea con me per darlo bello e pronto alla prof.ssa..... sai in
che casini.... sai le botte che partirebbero :-))
Cmq. per l'amore della libertà di cultura si rischia questo e altro ;-))
...tanto figurati che cultura ho da offrire io sul C ...bah.
> Io avevo scritto un messaggio con la spiegazione delle ottimizzazioni 1 e
2
> a "Kleidemos" <france...@tin.it>.
> Sei tu?!?
>
> Tommy
No mi spiace! Mai usato un nick del genere :(
Shaden
Tommy
"Shaden" <simonet...@virgilio.it.LEVATE.STO.MAIUSCOLO> wrote
> Spero entro breve di combinare qualcosa! Ancora una volta sei stato
> illuminante. :-)) Spero che postando il codice non lo rubi qualcuno che
sta
> in corso di laurea con me per darlo bello e pronto alla prof.ssa..... sai
in
> che casini.... sai le botte che partirebbero :-))
> Cmq. per l'amore della libertà di cultura si rischia questo e altro ;-))
> ...tanto figurati che cultura ho da offrire io sul C ...bah.
Beh, lascia stare allora, non lo postare.... non vorrei mai....
> 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
bumulo
> 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;
conviene controllare ad ogni passata; se l'elemento fuori posto fosse solo
uno
fai una passata e poi termini.
e per farlo basta una minima modifica:
> for(giri = 1; giri <= dim-1; giri++)
> {
-- booleana = 0; // Aggiunta da fare...
> for(j = 0; j <= dim-1-giri; j++)
>
così a ogni giro controlli se vengono o meno fatti scambi e in caso termini
> 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).
questa è parte dell'algoritmo di bubblesort e non è un'ottimizzazione...
> 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.
>
questa è invece una variante (con un nome ben preciso ma che non ricordo) e
da
i suoi vantaggi in abbinamento alla modifica che ti ho già detto ma solo su
vettori
parzialmente ordinati
> 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!! :-))
bene... sono contento (anche se penso che tu ti riferisca all'altro Tommy
:-p )
> Shaden
Bumulo (anch'io Tommy per l'anagrafe)
PS ti si rivede (rilegge) quando fai il mergesort??? :-))
Tommy
"bumulo" <bum...@yahoo.com> wrote
> conviene controllare ad ogni passata; se l'elemento fuori posto fosse solo
> uno
> fai una passata e poi termini.
> e per farlo basta una minima modifica:
Credo tu ti sia espresso male:
Non serve sapere se l'elemento fuori posto e' solo uno o no... serve sapere
se l'intero ciclo interno ha fatto qualche swap o no. Se non ne ha fatto
nessuno l'array e' gia' ordinato e si puo' quindi smettere. Se invece c'e'
stato anche solo uno swap allora non e' piu' detto che sia ordinato e quindi
bisogna continuare. Credo il concetto ti fosse chiaro, immagino ti sia solo
espresso male.
> > for(giri = 1; giri <= dim-1; giri++)
> > {
> -- booleana = 0; // Aggiunta da fare...
> > for(j = 0; j <= dim-1-giri; j++)
> >
> cosě a ogni giro controlli se vengono o meno fatti scambi e in caso
termini
Umh, hai ragione, Shaden si e' dimenticato di rimettere booleana a 0 ogni
volta. In questo modo il suo punto 1 non funziona di certo. Graze bumulo per
aver notato questo... io sono stato troppo pigro per controllare bene il suo
codice... ho pensato solo alle ottimizzazioni che lui proponeva!
Questa e' una buona ragione per vedere quanto e' piu' semplice usare un
while(!is_sorted).
> > 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).
> 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
bumulo
un dì Tommy scrisse:
> Credo tu ti sia espresso male:
rileggendomi effettivamente mi sono espresso male
ma dall'aggiunta al codice si capisce cosa intendevo...
>>> for(giri = 1; giri <= dim-1; giri++)
>>> {
>> -- booleana = 0; // Aggiunta da fare...
>>> for(j = 0; j <= dim-1-giri; j++)
>>>
> Umh, hai ragione, Shaden si e' dimenticato di rimettere booleana a 0
> ogni volta. In questo modo il suo punto 1 non funziona di certo.
> Graze bumulo per aver notato questo... io sono stato troppo pigro per
> controllare bene il suo codice... ho pensato solo alle ottimizzazioni
> che lui proponeva!
io invece l'avevo inteso come una cosa voluta, se è *già* ordinato non lo
ordino altrimenti faccio *tutto*
> Tommy
(Anch'io Tommy) as Bumulo
Tommy
"bumulo" <bum...@yahoo.com> wrote
> io invece l'avevo inteso come una cosa voluta, se è *già* ordinato non lo
> ordino altrimenti faccio *tutto*
Beh, potrebbe anche essere come dici tu... sarebbe tuttavia sciocco da parte
sua...
Quando Shaden ha detto:
>>>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
Tommy
"Shaden" <simonet...@virgilio.it.LEVATE.STO.MAIUSCOLO> wrote
> 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
Shaden
>
> PS ti si rivede (rilegge) quando fai il mergesort??? :-))
>
>
anche lo studio del mergesort...e temo ribiomberò qui :-PPP
...scusate la brevità ma devo scappare... giri burocratici mi
aspettano...che palle!!!
Shaden
Shaden
> > 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.
> >
> questa è invece una variante (con un nome ben preciso ma che non ricordo)
e
> da
> i suoi vantaggi in abbinamento alla modifica che ti ho già detto ma solo
su
> vettori
> parzialmente ordinati
Ho fatto un pò di ricerche in rete: l'algoritmo si chiama "Shaker Sort" , e
in effetti sembra dare vantaggi su algoritmi "quasi" ordinati.
...ci sentiamo dopo...vado e cerco di fondere insieme un pò di cose.
> Bumulo (anch'io Tommy per l'anagrafe)
>
> 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) :-))