Bubble sort in Java

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.