di Sergio Mauri
L’algoritmo di ordinamento a bolle (Bubble Sort) è uno degli algoritmi di ordinamento più semplici e intuitivi. Funziona confrontando ripetutamente coppie di elementi adiacenti e scambiandoli se sono nell’ordine sbagliato. L’algoritmo continua a passare attraverso la lista fino a quando non viene eseguito un passaggio senza effettuare alcuno scambio, indicando che la lista è stata ordinata. Ecco la sua formulazione:
- Iterazione attraverso l’array: l’algoritmo passa attraverso l’array di elementi dall’inizio alla fine.
- Confronto e scambio: per ogni coppia di elementi adiacenti, l’algoritmo confronta l’elemento corrente con il successivo. Se l’elemento corrente è maggiore dell’elemento successivo (nel caso di un ordinamento crescente), allora avviene uno scambio tra di loro.
- Passaggio attraverso l’array: l’algoritmo continua a passare attraverso l’array fino a quando non viene completato un passaggio senza effettuare alcuno scambio. Questo indica che l’array è stato ordinato con successo e l’algoritmo può terminare.
Ecco una rappresentazione della formula dell’algoritmo di Bubble Sort:
Per ogni i che va da 0 a lunghezza dell’array – 1:
Per ogni j che va da 0 a lunghezza dell’array – i – 1:
Se array[j] > array[j+1]:
Scambia(array[j], array[j+1])
Dove array è l’array da ordinare e Scambia(a, b) è una funzione che scambia gli elementi a e b.
La complessità dell’algoritmo di Bubble Sort è O(n^2) nel caso peggiore e medio, dove n è la dimensione dell’array da ordinare. Questo lo rende inefficace per grandi insiemi di dati, ma può essere utile per piccoli insiemi o come esempio didattico per capire il concetto di ordinamento.
