Bubble sort: differenze tra le versioni

Versione delle 08:19, 22 lug 2005

Versione delle 11:29, 3 ago 2005

Riga 1:

{{da controllare|firma=[[Utente:DanGarb|DanGarb]]|motivo=ci sono errori in alcune implementazioni (vedi discussione)}}

Il '''bubble sort''' o '''bubblesort''' (letteralmente: ''ordinamento a bollicine'') è un semplice [[algoritmo]] [[algoritmo di ordinamento|di ordinamento]] particolarmente indicato per l'ordinamento di [[array]]. Pur non essendo un algoritmo particolarmente efficiente (ha una [[complessità|complessità computazionale]] (misurata in termini di numero di confronti e [[assegnamento|assegnamenti]]) ''O(n²)'', molto superiore per esempio a quella del [[quicksort]]), è piuttosto noto e utilizzato (sia in ambito didattico che da parte di programmatori professionisti) in virtù della sua semplicità. Dell'algoritmo esistono numerose varianti, in alcuni casi sufficientemente note da aver meritato un nome distinto (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 [[relazione d'ordine]]; a fini illustrativi, in questo articolo ci riferiremo all'ordinamento di un array di [[numero intero|numeri interi]]. Il nome dell'algoritmo è dovuto al fatto che, durante l'applicazione del procedimento, i valori vengono spostati all'interno dell'array con una dinamica che ricorda il movimento delle bollicine in un bicchiere di [[champagne]]. 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 champagne, tuttavia, alcuni elementi ''salgono'' ma altri ''scendono'').