Bubble sort: differenze tra le versioni

Versione delle 19:19, 21 lug 2021

Versione delle 22:49, 11 ago 2021

Riga 14:

}}

[[File:Bubblesort-edited-color.svg|alt=Bubble sort colore modificato|frame|Svolgimento dell'algoritmo Bubblesort, versione colorata]]

In [[informatica]] il '''Bubble sort''' o ''ordinamento a bolla'' è un semplice [[algoritmo di ordinamento]] di una listaliste di dati. OgniIn esso l'insieme di dati viene scansionato, ogni coppia di elementi adiacenti viene comparata eed invertitai due elementi vengono invertiti di posizione se sono nell'ordine sbagliato. L'algoritmo continua nuovamente a ri-eseguire questi passaggi persu tutta la lista finchéfino a quando non vengono più eseguiti scambi, situazione che indica che la lista è ordinata.<ref>

{{Cita web

|url = https://stackoverflow.com/questions/tagged/bubble-sort

Riga 24:

== Denominazione ed efficienza ==

L'algoritmo deve il suo nome al modo in cui gli elementi vengono ordinati in una lista: quelli più piccoli "risalgono" verso un'estremità della lista, mentre quelli più grandi "affondano" verso l'estremità opposta della lista, come le bolle in un bicchiere dicontenente una bevanda champagnefrizzante. In particolare, alcuni elementi attraversano la lista velocemente (in gergo detti "''lepri''"), altri invece più lentamente (detti "''tartarughe''"). I primi vengono spostati nella stessa direzione in cui scorre l'indice dell'algoritmo, mentre i secondi nella direzione opposta.

Come tutti gli algoritmi di ordinamento, può essere usato per ordinare dati di un qualsiasi tipo per i quali sia definita una [[relazione d'ordine]].

Il Bubble sort è più efficiente rispetto al più semplice algoritmo di Ordinamento Ingenuo perché, invece di continuare ad eseguire sempre fino alla fine i due cicli annidati, si interrompe appena si accorge di non effettuare più scambi quando l'ordinamento è già completo. EssoSi hatratta comunque unadi un algoritmo non particolarmente efficiente, presentando uan [[Teoria della complessità computazionale|complessità computazionale]] dell'ordine di ''[[O-grande|O]]<math>(n^2)</math>'' confronti, con ''n'' elementi da ordinare., Perciòpertanto il suo utilizzo si limita a scopi didattici in virtù della sua semplicità e per introdurre i futuri programmatori al ragionamento algoritmico e alle misure di complessità.<ref>{{Cita libro|autore = Donald Knuth|titolo = The Art of Computer Programming Vol. 3|anno = 1973|editore = Addison Wesley|città = }}</ref>

Dell'algoritmo esistono numerose [[#Varianti e ottimizzazioni|varianti]], per esempio lo [[shaker sort]].

Riga 38:

Per esempio, saranno confrontati il primo e il secondo elemento, poi il secondo e il terzo, poi il terzo e il quarto, e così via fino al confronto fra il penultimo e l'ultimo elemento. Ad ogni confronto, se i due elementi confrontati non sono ordinati secondo il criterio prescelto, vengono scambiati di posizione. Durante ogni iterazione almeno un valore viene spostato rapidamente fino a raggiungere la sua collocazione definitiva; in particolare, alla prima iterazione il numero più grande raggiunge l'ultima posizione dell'array, alla seconda il secondo numero più grande raggiunge la penultima posizione, e così via.

Il motivo è semplice, e si può illustrare con un esempio. Supponiamo che l'array sia inizialmente disposto come segue:

15 6 4 10 11 2