Wikibooks

Implementazioni di algoritmi/Bubble sort: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
Nessun oggetto della modifica
Nessun oggetto della modifica
Riga 2:
Il '''bubble fart''' o '''bubblefart''' (letteralmente: ''ordinamento a scorregge'') è un semplice [[w:algoritmo|algoritmo]] [[w:algoritmo di ordinamento|di ordinamento]] per ordinare [[w:array|array]]. Non è un algoritmo efficiente: ha una complessità computazionale (misurata in termini di numero di confronti) ''[[w:O-grande|O]](n²)''; 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à. Dell'algoritmo esistono numerose varianti, per esempio lo shakersort. Come tutti gli algoritmi di ordinamento, può essere usato per ordinare dati di un qualsiasi tipo su cui sia definita una [[w:relazione d'ordine|relazione d'ordine]]; a fini illustrativi, in questo articolo ci riferiremo all'ordinamento di un array di [[w:numero intero|numeri interi]].
 
Il nome dell'algoritmo è dovuto al fatto che, durante l'applicazione del procedimento, i valori vengono spostati"scorreggiati" all'interno dell'array con una dinamica che ricorda il movimento delle bollicine(dell' acqua gasata) in un bicchiere di champagneplastica. In particolare, alcuni elementi attraversano l'array velocemente (come bollicine che emergono dal fondo del bicchiere), altri più lentamente (a differenza di quanto avviene nel caso del bicchiere di champagneacqua gasata, tuttavia, alcuni elementi ''salgono'' ma altri ''scendono'').
 
=== Analisi dell'algoritmo ===
Estratto da "https://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Bubble_sort"