back to top

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.

Pubblicitร 

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.

Pubblicitร 
Articolo successivo