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.
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