Bubble sort

Il bubble sort è l'algoritmo di ordinamento più semplice da descrivere: confronta due vicini, scambiali se sono nell'ordine sbagliato e ripeti. È lento sulle liste lunghe, ma ogni passo è facile da seguire, ed è per questo il classico primo algoritmo da guardare.

Barre di altezze diverse in fase di ordinamento, due vicine evidenziate per uno scambio e le più alte già al loro posto in fondo
Barre di altezze diverse in fase di ordinamento, due vicine evidenziate per uno scambio e le più alte già al loro posto in fondo

L'idea

Percorri la lista da sinistra a destra e guarda ogni coppia di vicini. Se il valore a sinistra è più grande di quello a destra, scambiali. Quando arrivi in fondo, il valore più grande è stato portato fino all'ultimo posto, come una bolla che sale in superficie. Questo percorso si chiama passata. Ripeti le passate finché la lista è ordinata.

Un esempio

Prendi 5, 1, 4, 2, 8. La prima passata confronta 5 e 1 e li scambia, poi 5 e 4 (scambio), 5 e 2 (scambio) e 5 e 8 (nessuno scambio): 1, 4, 2, 5, 8. L'8 ora è al suo posto definitivo. La seconda passata confronta 1 e 4 (nessuno scambio), 4 e 2 (scambio) e 4 e 5 (nessuno scambio): 1, 2, 4, 5, 8. La terza passata non fa alcuno scambio, quindi la lista è ordinata: 9 confronti e 4 scambi.

Perché ogni passata sistema un valore in più

Durante una passata, il valore più grande visto finora viene sempre trascinato avanti: appena la passata lo raggiunge, ogni confronto lo sposta di un posto a destra. Così la prima passata mette il valore più grande in fondo, la seconda il secondo più grande subito prima, e così via. Dopo la passata k gli ultimi k posti sono definitivi, e la passata successiva può fermarsi un posto prima. Ecco perché le passate si accorciano.

Scambi uguali alle inversioni

Un'inversione è una coppia di valori nell'ordine sbagliato: un valore più grande da qualche parte prima di uno più piccolo. Scambiare due vicini fuori ordine elimina esattamente un'inversione e non ne crea altre. Quindi il bubble sort fa esattamente tanti scambi quante sono le inversioni della lista iniziale, in qualunque ordine arrivino i confronti. Una lista ordinata non ne ha; una lista inversa di n valori ne ha n(n − 1)/2, il massimo possibile.

L'arresto anticipato e il costo

Se un'intera passata non fa scambi, ogni vicino è in ordine e la lista è ordinata. Questo controllo permette al bubble sort di finire una lista ordinata in una sola passata di n − 1 confronti. Nel caso peggiore servono comunque n − 1 passate e n(n − 1)/2 confronti, e in media il numero di scambi è n(n − 1)/4. Entrambi crescono con n², quindi raddoppiare la lista rende l'ordinamento circa quattro volte più lungo.

Il bubble sort è stabile: i valori uguali non si scambiano mai, quindi mantengono il loro ordine. Ordina sul posto, senza memoria aggiuntiva. L'insertion sort ha le stesse proprietà e di solito richiede meno passi, mentre il merge sort e il quicksort richiedono un tempo proporzionale a n log n, molto meno sulle liste lunghe.

Provalo

Apri l'app e premi Avvia, oppure premi Passo per procedere un confronto alla volta. I due valori confrontati sono evidenziati, uno scambio ha un colore tutto suo e i valori già al loro posto diventano verdi. Prova una lista inversa per vedere il caso peggiore, una quasi ordinata per vedere l'arresto anticipato chiudere l'ordinamento dopo poche passate, o inserisci i numeri dell'esempio qui sopra.

Domande frequenti

Qual è la complessità temporale del bubble sort?

O(n²) nel caso peggiore e in quello medio: fino a n(n − 1)/2 confronti per n valori. Con l'arresto anticipato, una lista già ordinata richiede O(n), una sola passata. Serve solo O(1) di memoria aggiuntiva.

Il bubble sort è stabile?

Sì. Scambia due vicini solo quando quello a sinistra è strettamente più grande, quindi i valori uguali non si superano mai e mantengono il loro ordine originale.

Che differenza c'è tra bubble sort e insertion sort?

Entrambi scambiano vicini ed entrambi fanno tanti scambi quante sono le inversioni. Il bubble sort fa passate complete sulla parte non ordinata; l'insertion sort fa scorrere indietro ogni nuovo valore solo quanto serve, quindi di solito fa meno confronti, soprattutto sulle liste quasi ordinate.

Quando conviene il bubble sort?

Soprattutto per insegnare, e per liste molto corte dove la semplicità conta più della velocità. Per tutto il resto, l'ordinamento integrato nel tuo linguaggio di programmazione è molto più veloce.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Prova il bubble sort