Discussione:Bubble sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m aggiungo template |
|||
| (34 versioni intermedie di 17 utenti non mostrate) | |||
Riga 1:
{{Wikiscuola
|materiaSUP = informatica
}}
==Non è così inutile!==
L'articolo dice:
si usa solamente a scopo didattico in virtù della sua semplicità, e per introdurre i futuri programmatori al ragionamento algoritmico e alle misure di complessità.
Tuttavia il bubble-sort ha i suoi usi, in computer Graphics ad esempio viene utilizzata quando si mantiene una lista di oggetti ordinati per distanza da un punto o per profondità lungo un asse. Solitamente la lista rimane quasi del tutto ordinata e accadono piccoli cambiamenti ad ogni time-frame. Il bubble-sort in questa occasione, come in altri casi, ha tempi di esecuzione più brevi di altri algoritmi più avanzati. Inoltre può essere implementato in modo che venga eseguita una singola iterazione per elemento per ogni frame in modo da avere tempi di esecuzione O(n) quando non è fondamentale che la lista sia perfettamente ordinata.
FedeDevi.
==Lo XOR==
Usare lo XOR nel C++ per scambiare dati è sconsigliato da qualunque manuale di buona programmazione: un compilatore ottimizzante fa meglio da solo. e poi esiste std::swap. Provvedo a modificare e metto qui il codice incriminato
Riga 24 ⟶ 35:
}
[[Utente:Blakwolf|<
== ERRORI ??? ==
Riga 36 ⟶ 46:
C'era comunque un errore (a=elemN!) l'ho corretto e ho cambiato i cicli (per come erano non c'era l'effetto bolla), ho anche introdotto un'ottimizzazione che comunque è prevista nell'algoritmo originale (ma manca nella discussione).
Io elminerei anche i ''register'' in quanto è buona norma lasciar fare al compilatore[[Utente:Bermas66|bermas66]] 09:05, Lug 21, 2005 (CEST)<br/>
* Non saprei, la parola chiave ''register'' in effetti ''lascia'' fare al compilatore (il suo significato letterale potrebbe essere reso con: "questa variabile verrà usata molto frequentemente nelle prossime istruzioni, se possibile sarebbe utile mantenerla in un registro di CPU"... [[Utente:Moongateclimber|Moongateclimber]]<br/>▼
** Mi pare che così com'è il programma non funzioni. Credo sia fondamentale che i due cicli abbiano andamento opposto: una sale e l'altro scende. Consiglio di guardare [http://wikisource.org/wiki/bubble_sort qui]. bye [[Utente:DanGarb|DanGarb]] 10:49, Lug 21, 2005 (CEST)<br/>▼
***Non
*** Il programma in C così com'è non funziona. Basta applicarlo al seguente array : [2,1] oppure a [3,2,1] . Un bug banale dipende dal fatto che l'elemento 0 non viene mai toccato. Anche correggendo questo piccolo bug però il programma non funzionerebbe comunque poiché il primo elemento verrebbe scambiato al più una sola volta. IMHO i due cicli devono essere opposti, anche se devo ammettere che sono anni che non leggo libri di informatica. bye [[Utente:DanGarb|DanGarb]] 11:31, Lug 21, 2005 (CEST)<br/>
****Sulla cella 0 avevi chiaramente ragione, sui cicli invertiti posso dirti... fidati! Spiego il bubblesort in corsi di C da anni, ce ne sono N varianti equivalenti da tutti i punti di vista. Vero che forse sarebbe più chiaro che tutti gli esempi di codice si rifacessero alla stessa versione (cosa che adesso non e'), e magari potrei aggiungere una sezione ''varianti e ottimizzazioni''... che ne dite?[[Utente:Moongateclimber|Moongateclimber]]
***** Scusate se insisto, fidarsi è bene ma non fidarsi è meglio :-]. Insisto perché dal mio punto di vista è palese che il programma in C non faccia il suo dovere, ovvero non ordini i vettori. Per una verifica certa occorrerebbe implementarlo e testarlo. Qui proverò con qualche ragionamento e con un controesempio a convincervi: (anche se contrariamente a quanto ho detto prima, il programma può essere implementato con entrambi i cicli crescenti; in questa maniera :'''for (b=0; b<elemN-a-1; ++b)'''). Il ragionamento che confuta l'attuale versione: per ''a=0'' il primo elemento dell'array è confrontato col secondo ed eventualmente scambiato; per i successivi valori di ''a'' il primo elemento non viene più toccato... quindi ==> se l'elemento minore del sistema non è in prima o seconda posizione ne consegue che non potrà mai arrivare in prima posizione. Il controesempio : array = (2,3,1) a=0 b=0 --> (''2'',''3'',1) a=0 b=1 (2,''1'',''3'') --> a=1 b=1 (2,''1'',''3'') --> fine programma . Bye [[Utente:DanGarb|DanGarb]] 13:40, Lug 21, 2005 (CEST)
******Scusami, hai assolutamente ragione anche questa volta. Il problema è che se entrambi i cicli vanno in avanti, quello + interno dovrebbe avere una forma del tipo: "for(b=0; b<nElem-1; b++)", o ancora meglio (ottimizzato) "for(b=0; b<nElem-1-a; b++)", cioe' l'indice deve partire da 0 (non da a). Ho avuto un po' fretta nel risponderti, chiedo venia :-((
****** A questo punto direi che siamo d'accordo Moongateclimber. :-) . Lascio comunque l'indicazione ''da controllare'' perché sarà opportuno dare un'occhiata anche agli altri linguaggi. Da una prima occhiata veloce, per quel che capisco qualche bug è ancora presente. Ora non ho tempo, spero di riuscire a darci un'occhiata più tardi. Mi sembri un esperto del ramo. Se hai tempo dacci un'occhiata anche tu. Alla prossima [[Utente:DanGarb|DanGarb]] 15:13, Lug 21, 2005 (CEST)
Prego, accomodati. se la pagina viene esageratamente lunga, si fa un articolo a parte, tipo [[Varianti del Bubblesort in C]], e si inserisce prima del codice la nota
:''Il codice riportato è a fini didattici. Per una descrizione completa e approfondita, mirata anche all'ottimizzazione, vedi l'articolo [[Varianti del Bubblesort in C]]''
[[Utente:Blakwolf|<span style="color:black">'''BW'''</span>]] [[Discussioni utente:Blakwolf|Insultami]] 12:06, Lug 21, 2005 (CEST)
Ho modificato di nuovo il codice C, ora è molto più coerente con la descrizione
----
Gentili ragazzi: stavo basandomi sulle vostre pagine per superare un esame di ingegneria e devo ammettere che quando parlate di questi algoritmi di ricerca girate un pò intorno al problema, perfavore siate più precisi e fate delle implementazioni più chiare!! E soprattutto evitate un sacco di spiegazioni inutili!!
Basandomi su queste pagine ho solo perso due ore di tempo per capire che in realtà l'algoritmo non era sinteticamente spiegato, la codifica era astrusa e incomprensibile e per di più ci sono un sacco di errori!! Regà siate più chiari!!! Grazie
Forse se mi gira ve la metto io un implementazione chiara in java: evitate di usare i riferimenti a gli oggetti e le classi tipo clone o isequal perchè si sta parlando di altro!!! Senza offesa e saluti a tutti gli informatici
==Ricominciamo dal C==
Allora, visto che si parla di ottimizzazioni, direi che si può partire dal [[KISS]], e quindi:
#è inutile dichiarare register le variabile su un codice didattico
#altrettanto inutile è ottimizzare via qualche ciclo
#se proprio vogliamo mettere l'algoritmo più ottimizzabile, mettiamo quello inverso, che parte dalla fine, cioè
<pre>
void bubbleSort(int *array, int lunghezza)
{
int a, b, temp;
for(a = lunghezza - 1; a > 0; --a)
for(b = 0; b < a; ++b)
if(array[b] > array[b+1])
{
temp = array[b];
array[b] = array[b+1];
array[b+1] = temp;
}
}
</pre>
Oltre ad essere il più breve, è anche quello che un compilatore ottimizzante gestisce meglio. Non serve nemmeno tener conto degli scambi...
Che ne dite? --[[Utente:Blakwolf|<span style="color:black">'''BW'''</span>]] [[Discussioni utente:Blakwolf|Insultami]] 08:43, Lug 22, 2005 (CEST)
---
Sono d'accordo con te, su tutti i punti. Inoltre credo che la struttura del programma debba essere la stessa in tutti i linguaggi. Eventualmente si potrebbe scegliere il C per inserire anche una versione ottimizzata. bye [[Utente:DanGarb|DanGarb]] 08:54, Lug 22, 2005 (CEST)
== Implementazioni ==
Ricordo a tutti che le implementazioni in specifici linguaggi vanno messe su Wikibooks, come da [[Discussioni_progetto:Informatica/Archivio/2008#Codice_sorgente_nelle_voci|decisione della comunità]]. Il link a wikibooks è in fondo alla voce, nella sezione Altri progetti. Grazie. --[[Utente:Baruneju|Giuseppe]] ([[Discussioni utente:Baruneju|msg]]) 16:40, 27 gen 2010 (CET)
== Modifica del secondo pseudocodice ==
Ho modificato leggermente il secondo pseudocodice: quest'ultimo infatti è un miglioramento del primo, quello base, e verte sul fatto che ad ogni iterazione si può ridurre di una unità il ciclo for. Quindi, al pari di quello base, esso deve fermarsi quando non sono più stati effettuati scambi e non quando ''alto'' (che ho rinominato ''n'' per maggiore semplicità) va a zero. Infatti, più che un miglioramento si tratterebbe in tal caso di un peggioramento: quello base, ad esempio, uscirebbe subito se la lista fosse già ordinata mentre il secondo codice che dovrebbe essere migliore scandirebbe inutilmente tutte le iterazioni.--[[Utente:Zetazeti|Zetazeti]] ([[Discussioni utente:Zetazeti|msg]]) 02:57, 23 gen 2015 (CET)
:Carino. Grazie per averlo inserito!
:L'analisi di complessità che hai introdotto, però, è molto vaga. Assumi forse uniforme distribuzione di probabilità dei valori? Potresti, in ogni caso, spiegare meglio da dove tiri fuori il dimezzamento dei tempi?
:--[[Utente:Soujak|SoujaK]] ([[Discussioni utente:Soujak|msg]]) 17:17, 23 gen 2015 (CET)
::Grazie dell'osservazione: rileggendola nuovamente non posso non condividere che la frase è troppo approssimativa. L'avevo tradotta direttamente dal corrispondente articolo inglese senza soffermarmi troppo. Non si può dire che si risparmia almeno il 50% dei confronti. Se ad esempio considero una lista già ordinata in partenza allora sia lo pseudocodice base, sia il terzo pseudocodice faranno la stessa cosa: usciranno alla conclusione del primo passaggio dopo aver effettuato lo stesso numero di confronti.--[[Utente:Zetazeti|Zetazeti]] ([[Discussioni utente:Zetazeti|msg]]) 00:18, 24 gen 2015 (CET)
== Immagine ==
Utilizzerei questa [[:File:Sorting bubblesort anim.gif]] che descrive IMHO meglio l'algoritmo --[[Utente:Valerio Bozzolan|Valerio Bozzolan]] ([[Discussioni utente:Valerio Bozzolan|msg]]) 17:39, 11 ott 2016 (CEST)
▲--[[Utente:Bermas66|bermas66]] 09:05, Lug 21, 2005 (CEST)
▲** Mi pare che così com'è il programma non funzioni. Credo sia fondamentale che i due cicli abbiano andamento opposto: una sale e l'altro scende. Consiglio di guardare [http://wikisource.org/wiki/bubble_sort qui]. bye [[Utente:DanGarb|DanGarb]] 10:49, Lug 21, 2005 (CEST)
== Bubble sort è stabile ==
▲***Non e' necessario che gli andamenti siano opposti; su molti libri l'algoritmo viene riportato con i 2 cicli in uguale direzione. Ogni ciclo interno posiziona nella cella definitiva ''almeno'' uno dei valori non ancora a posto. Purche' il ciclo esterno comporti N iterazioni (dimensione array), alla fine tutti gli elementi sono a posto. Il ciclo inverso rende semplicemente piu' semplice esprimere gli indici di partenza e di arrivo dei confronti.[[Utente:Moongateclimber|Moongateclimber]]
Per quanto primitivo, bubble-sort ha un vantaggio su tanti tipi di algoritmi più veloci fra cui quick-sort: è stabile, non distrugge cioè l'ordine di chiavi che siano già state ordinate (non sono sicuro che questo fatto sia citato nel libro di Knuth). Se per esempio ordini una lista di clienti nella chiave 'cognome', puoi poi ordinarli nella chiave 'città' ottenendo una lista nella quale sotto ogni città i clienti son ordinati secondo il cognome. Se invece usi per esempio quick-sort per questo secondo ordinamento alla fine l'ordine dei cognomi è solitamente di nuovo casuale. Questa proprietà è discussa in generale in [[Algoritmo_di_ordinamento#Stabilità_di_un_algoritmo]] e mi sembra che se ne dovrebbe parlare anche in quest'articolo, dato che è piuttosto importante. [[Speciale:Contributi/194.174.73.80|194.174.73.80]] ([[User talk:194.174.73.80|msg]]) 13:46, 5 nov 2018 (CET) Marco Pagliero Berlin
▲* Non saprei, la parola chiave ''register'' in effetti ''lascia'' fare al compilatore (il suo significato letterale potrebbe essere reso con: "questa variabile verrà usata molto frequentemente nelle prossime istruzioni, se possibile sarebbe utile mantenerla in un registro di CPU"... [[Utente:Moongateclimber|Moongateclimber]]
:Vedi [[WP:BOLD]] :-) --[[User:Horcrux|Horcrux]] ([[User talk:Horcrux|msg]]) 16:05, 5 nov 2018 (CET)
| |||