Tra i piรน semplici algoritmi di ordinamento di Java, troviamo il Bubble Sort, che in italiano significa naturalmente ordinamento a bolle.
Il meccanismo di funzionamento si basa sull’idea di far emergere man mano (come bollicine) gli elementi minori verso l’inizio del vettore, mentre contemporaneamente quelli maggiori si posizionano in fondo al vettore.
Come funziona il Bubble Sort
Vediamo nel dettaglio l’algoritmo: dato un vettore con n elementi, per ogni iterazione il primo elemento viene confrontato con il secondo; se il primo risulta maggiore, i due elementi vengono scambiati. La stessa operazione avviene tra il secondo ed il terzo elemento e cosรฌ via fino alla fine del vettore.
Dopo n-1 iterazioni, il nostro vettore risulterร ordinato. Questo processo continua fino a quando non vengono effettuati piรน scambi.
Esempio di implementazione in Java
Ecco l’implementazione in Java dell’algoritmo Bubble Sort:
public void bubbleSort(int[] array) {
for (int i = 0; i < array.length; i++) {
boolean flag = false;
for (int j = 0; j < array.length - 1; j++) {
// Se l'elemento j รจ maggiore del successivo, scambiamo i valori
if (array[j] > array[j + 1]) {
int k = array[j];
array[j] = array[j + 1];
array[j + 1] = k;
flag = true; // Indica che รจ avvenuto uno scambio
}
}
if (!flag) break; // Se flag รจ false, l'array รจ giร ordinato
}
}
Analisi della complessitร dell’Algoritmo
La complessitร dell’algoritmo in termini di numero di confronti รจ quadratica nel caso peggiore e medio, che si esprime come O(nยฒ). Tuttavia, nel caso migliore (quando il vettore รจ giร ordinato o parzialmente ordinato), la complessitร risulta lineare, ovvero O(n).
Per quanto riguarda gli scambi, la complessitร rimane quadratica nel caso peggiore e medio O(nยฒ), mentre risulta costante O(1) nel miglior caso. Questo rende il Bubble Sort meno efficiente rispetto ad altri algoritmi di ordinamento, come il Merge Sort o il Quick Sort, specie per set di dati di grandi dimensioni.
Quando utilizzare Bubble Sort
Nonostante la sua efficienza limitata, il Bubble Sort รจ spesso utilizzato per introdurre i concetti di base dell’ordinamento agli studenti di programmazione. ร semplice da implementare e comprendere, ma raramente รจ utilizzato in applicazioni pratiche dove sono richiesti algoritmi di ordinamento piรน veloci e piรน efficienti.