Discussione:Bubble sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m orto: |
m aggiungo template |
||
| (20 versioni intermedie di 13 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 47 ⟶ 58:
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|<
Riga 53 ⟶ 64:
--[[Utente:Bermas66|bermas66]] 19:16, Lug 21, 2005 (CEST)
----
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==
Riga 75 ⟶ 93:
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|<
---
Riga 81 ⟶ 99:
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)
== Bubble sort è stabile ==
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
:Vedi [[WP:BOLD]] :-) --[[User:Horcrux|Horcrux]] ([[User talk:Horcrux|msg]]) 16:05, 5 nov 2018 (CET)
| |||