# Implementazioni di algoritmi/Bubble sort

Implementazioni di algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaImplementazioni di algoritmi/Copertina
* Algoritmo di EuclideImplementazioni di algoritmi/Algoritmo di Euclide
* Elevazione a potenzaImplementazioni di algoritmi/Elevazione a potenza
* Prodotto scalareImplementazioni di algoritmi/Prodotto scalare
* Calcolo della PasquaImplementazioni di algoritmi/Calcolo della Pasqua
* Metodo Monte CarloImplementazioni di algoritmi/Metodo Monte Carlo
* Ricerca
** Ricerca dicotomicaImplementazioni di algoritmi/Ricerca dicotomica
* Numeri primi
** Crivello di EratosteneImplementazioni di algoritmi/Crivello di Eratostene
** Test di primalità
*** Test deterministicoImplementazioni di algoritmi/Test deterministico
*** Test di Miller-RabinImplementazioni di algoritmi/Test di Miller-Rabin
* PRNG
** Mersenne TwisterImplementazioni di algoritmi/Mersenne Twister
** Test Chi QuadratoImplementazioni di algoritmi/Test Chi Quadrato
* Crittografia
** RSAImplementazioni di algoritmi/RSA
** TEAImplementazioni di algoritmi/TEA
* π(Metodi per definire il pi greco)
** Pi grecoImplementazioni di algoritmi/Pi greco
* Algoritmi di ordinamento
** Bubble sortImplementazioni di algoritmi/Bubble sort
** Bucket sortImplementazioni di algoritmi/Bucket sort
** Counting sortImplementazioni di algoritmi/Counting sort
** Gnome sortImplementazioni di algoritmi/Gnome sort
** Insertion sortImplementazioni di algoritmi/Insertion sort
** Merge sortImplementazioni di algoritmi/Merge sort
** QuicksortImplementazioni di algoritmi/Quicksort
** Radix sortImplementazioni di algoritmi/Radix sort
** Selection sortImplementazioni di algoritmi/Selection sort
** Shaker sortImplementazioni di algoritmi/Shaker sort
** Shell sortImplementazioni di algoritmi/Shell sort
Modifica il sommario
Il bubble sort o bubblesort (letteralmente: ordinamento a bolle) è un semplice algoritmo di ordinamento per ordinare array. Non è un algoritmo efficiente: ha una complessità computazionale (misurata in termini di numero di confronti) 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 relazione d'ordine; a fini illustrativi, in questo articolo ci riferiremo all'ordinamento di un array di 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).

### Analisi dell'algoritmo

Il bubble sort effettua all'incirca ${\frac {N^{2}}{2}}$ confronti ed ${\frac {N^{2}}{2}}$ scambi sia in media che nel caso peggiore. Il tempo di esecuzione dell'algoritmo è Θ(n$^2$).

## Implementazioni

Seguono alcune implementazioni in vari linguaggi. Le implementazioni nei diversi linguaggi non si riferiscono necessariamente alla stessa variante dell'algoritmo.

### C++

tmp è dichiarata di tipo int, quindi dovrà contenere interi; se l'array contiene elementi di tipo diverso, sarà sufficiente modificare la sua dichiarazione.

### Java

Implementazione dell'algoritmo che presenta le ottimizzazioni enunciate alla voce Bubble sort:
Algoritmo implementato sui vector, in questo esempio, di oggetti di tipo String:
Segue una documentata implementazione Java dell'algoritmo di sort a bolle,
pensata da uno studente del dipartimento di informatica (ITPS) di Bari:

### AppleScript

Nota: AppleScript è 1-based, cioè il primo elemento di una lista è 1

### MATLAB
## Altri progetti

Altri progetti
* Wikipedia
* Wikimedia Commons
* Wikipedia contiene una voce su questo algoritmo
* Wikimedia Commons contiene immagini o altri file su bubble sort