Bubble sort: differenze tra le versioni

Versione delle 13:02, 27 giu 2024

Versione delle 16:24, 19 ott 2024

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 liste di dati. In esso l'insieme di dati viene scansionato, ogni coppia di elementi adiacenti viene comparata ed i due elementi vengono invertiti di posizione se sono nell'ordine sbagliato. L'algoritmo continua nuovamente a ri-eseguire questi passaggi su tutta la lista 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 28:

Come tutti gli algoritmi di ordinamento, può essere usato per ordinare dati di 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. Si tratta comunque di un algoritmo non particolarmente efficiente, presentando una [[Teoria della complessità computazionale|complessità computazionale]] dell'ordine di ''[[O-grande|O]]<math>(n^2)</math>'' confronti, con ''n'' elementi da ordinare, 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 36:

Il bubble sort è un [[algoritmo iterativo]], ossia basato sulla ripetizione di un procedimento fondamentale. La singola iterazione dell'algoritmo prevede che gli elementi dell'array siano confrontati a due a due, procedendo in un verso stabilito (che si scorra l'array a partire dall'inizio in avanti, o a partire dal fondo all'indietro, è irrilevante; d'ora in poi ipotizzeremo che lo si scorra partendo dall'inizio).

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:

Riga 55:

# alla iterazione i-esima, le ultime i-1 celle dell'array ospitano i loro valori definitivi, per cui la sequenza di confronti può essere terminata col confronto dei valori alle posizioni N+1-i e N-i.

Ovviamente, a ogni iterazione può accadere che più numeri vengano spostati; per cui, oltre a portare il numero più grande in fondo, ogni singola iterazione può contribuire anche a un riordinamento parziale degli altri valori. Anche per questo motivo, può accadere (e normalmente accade) che l'array risulti effettivamente ordinato ''prima'' che si sia raggiunta la N-1ª iterazione. Su questa osservazione sono basate le versioni ottimizzate dell'algoritmo.

=== Analisi dell'algoritmo ===

Riga 62:

=== Varianti e ottimizzazioni ===

Esistono numerose varianti del bubble sort, molte delle quali possono essere definite ottimizzazioni, in quanto mirano a ottenere lo stesso risultato finale (l'ordinamento dell'array) eseguendo, in media, meno operazioni, quindi impiegando meno tempo e meno risorse computazionali.

Un insieme di ottimizzazioni si basa sull'osservazione che, se, in una data iterazione, non avviene più alcuno scambio, significa che l'array è necessariamentesicuramente ordinato, equindi l'algoritmo può essere terminato anticipatamente (ovvero senza giungere alla N-1ª iterazione). Una tecnica di ottimizzazione può dunque essere applicata usando una variabile [[logica booleana|booleana]] (o equivalente) usata come "''[[flag]]''" che indicatiene traccia se nell'iterazione corrente si è eseguito almeno uno scambio. La variabile viene reimpostataimpostata a ''false'' all'inizio di ogni iterazione, e impostatamodificata a ''true'' solo nel caso in cui si proceda a uno scambio. Se al termine di una iterazione completa il valore della variabile ''flag'' è rimasto ''false'', ovvero nell'iterazione non sono stati eseguiti scambi, l'array è ordinato e l'intero algoritmo viene terminato. Questa tecnica produce una riduzione del tempo ''medio'' di esecuzione dell'algoritmo, pur con un certo [[overhead]] costante (dato dall'assegnamento e dal confronto della variabile ''flag'').

Una seconda linea di ottimizzazione (che può essere combinata con la prima) è basata sull'osservazione che (sempre assumendo una scansione dell'array, per esempio, in avanti, e ordinamento crescente) se una data iterazione non sposta nessun elemento di posizione maggiore di un dato valore ''i'', allora si può facilmente dimostrare che nessuna iterazione successiva eseguirà scambi in posizioni successive a tale valore ''i''. L'algoritmo può dunque essere ottimizzato memorizzando l'indicela posizione a cui avviene l'ultimo scambio durante una iterazione, e limitando le iterazioni successive alla scansionescansioni dell'array durante le iterazioni successive solo fino a tale posizione. Anche questa tecnica evidentemente introduce un piccolo ''overhead'', dato dalla (gestione delladi una variabile aggiuntiva che indica la posizione alla quale la scansione della lista deve fermarsi di ultimavolta in modifica)volta.

Un'altra variante già menzionata, (lo ''shakersortshaker sort''), consente di ridurre la probabilità che si verifichi la situazione di [[analisi del caso peggiore|caso peggiore]], (in cui tutte le ottimizzazioni precedentemente citate falliscono e quindi contribuiscono solo negativamente con i relativi ''overhead''); vedi [[Shaker sort|la voce relativa]].

=== Conigli e tartarughe ===

Riga 84:

== Pseudocodice ==

Di seguito viene riportato louno [[pseudocodice]] base relativo alla versione originale dell'algoritmo:

'''procedure''' BubbleSort(A''':'''lista degli elementi da ordinare)