L'ordinamento a bolle (bubble sort) in Python
In questa lezione implementerai il bubble sort e aggiungerai l'arresto anticipato quando la lista è già ordinata.
Introduzione
Il problema
L'ordinamento è ovunque, e capire come funziona aiuta a ragionare sulla velocità. Il bubble sort è l'algoritmo di ordinamento più facile da seguire passo dopo passo, per questo di solito è il primo che si studia, anche se nei programmi veri se ne usano di più veloci.
Immaginalo così
Il bubble sort è come mettere in fila dei bambini per altezza scambiando sempre e solo due vicini. Percorri la fila e scambi ogni coppia in cui il bambino più alto sta davanti. Dopo un giro il bambino più alto è arrivato in fondo, come una bolla che sale in superficie. Ripeti finché un giro non richiede scambi.
result[index] > result[index + 1]👫 Il bambino più alto sta davanti?result[index], result[index + 1] = ...🔄 Scambia i due vicinifor end in range(len(result) - 1, 0, -1):🚶 Ripercorri la fila, ogni volta un bambino in menoif not swapped: break✅ Nessuno scambio in un giro intero: la fila è ordinataIl bubble sort percorre ripetutamente la lista, scambiando gli elementi vicini nell'ordine sbagliato, finché una passata completa non fa nessuno scambio. In generale richiede tempo O(n²).
Punti chiave
result = values.copy()ordina una copia, così la lista del chiamante non cambia.if result[index] > result[index + 1]:scambia una coppia nell'ordine sbagliato.endsi riduce dopo ogni passata, perché i valori più grandi sono già in fondo.if not swapped: breaksi ferma prima quando una passata non fa scambi, quindi un input già ordinato finisce dopo una passata.
Quando si usa?
- Imparare come funziona l'ordinamento basato sui confronti.
- Liste piccolissime in strumenti didattici e animazioni.
- Controllare in una passata se una lista è già ordinata.
Quando non serve
- Qualsiasi programma vero:
sorted()elist.sort()sono molto più veloci (O(n log n)) e testati. - Liste di più di qualche centinaio di elementi: il numero di confronti cresce con il quadrato della lunghezza.
Visualizzatore di L'ordinamento a bolle (bubble sort) in Python
O(n²)Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.
Codice di esempio
def bubble_sort(values):
result = values.copy()
for end in range(len(result) - 1, 0, -1):
swapped = False
for index in range(end):
if result[index] > result[index + 1]:
result[index], result[index + 1] = result[index + 1], result[index]
swapped = True
if not swapped:
break
return result
print(bubble_sort([5, 1, 4, 2, 8]))
Risultato dell'esecuzione
[1, 2, 4, 5, 8]
Spiegazione del codice
Dopo ogni passata, il valore più grande della parte non ordinata è già nella posizione finale, quindi la passata successiva è più corta di un elemento. La variabile swapped registra se c'è stato almeno uno scambio. Se non ce n'è stato nessuno, la lista è già ordinata e il ciclo si ferma prima. Nel caso peggiore la complessità è O(n²), quindi non è adatto a grandi quantità di dati.
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi di approfondimento
Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.
- Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
- Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
- Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Errori comuni
Andare un indice troppo in là
result[index + 1] va oltre la fine quando index arriva all'ultima posizione.
for index in range(len(result)):
if result[index] > result[index + 1]:
for index in range(end):
if result[index] > result[index + 1]:
Hai finito questa lezione?
Segnala come imparata per tenere traccia dei tuoi progressi.
Esercitati con una sfida
Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.
- Count Inversions Count the out-of-order pairs in a list. Difficile
- Mediana di una Lista Trova il valore centrale di una lista dopo averla ordinata. Facile