Discussione:Bubble sort: differenze tra le versioni

Versione delle 11:18, 20 dic 2011

Versione attuale delle 14:15, 31 lug 2020

(11 versioni intermedie di 7 utenti non mostrate)

Riga 1:

{{Wikiscuola

|materiaSUP = informatica

}}

==Non è così inutile!==

L'articolo dice:

Riga 32 ⟶ 35:

}

[[Utente:Blakwolf|<fontspan colorstyle="color:black size +1">'''BW'''</fontspan>]] [[Discussioni utente:Blakwolf|Insultami ]] 09:27, Nov 29, 2004 (UTC)

== ERRORI ??? ==

Riga 55 ⟶ 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|<fontspan style="color=:black size +1">'''BW'''</fontspan>]] [[Discussioni utente:Blakwolf|Insultami]] 12:06, Lug 21, 2005 (CEST)

Riga 90 ⟶ 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|<fontspan style="color=:black size +1">'''BW'''</fontspan>]] [[Discussioni utente:Blakwolf|Insultami]] 08:43, Lug 22, 2005 (CEST)

---

Riga 98 ⟶ 101:

== Implementazioni ==

Ricordo a tutti che le implementazioni in specifici linguaggi vanno messe su Wikibooks, come da [[Discussioni_progetto:Informatica/Archivio6Archivio/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)