Algoritmi Python

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.

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

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.

Dalla fila di bambini al codice
result[index] > result[index + 1]👫 Il bambino più alto sta davanti?
result[index], result[index + 1] = ...🔄 Scambia i due vicini
for end in range(len(result) - 1, 0, -1):🚶 Ripercorri la fila, ogni volta un bambino in meno
if not swapped: break✅ Nessuno scambio in un giro intero: la fila è ordinata
Dopo ogni passata, il valore più grande rimasto è al suo posto finale.
In una frase

Il 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

  1. result = values.copy() ordina una copia, così la lista del chiamante non cambia.
  2. if result[index] > result[index + 1]: scambia una coppia nell'ordine sbagliato.
  3. end si riduce dopo ogni passata, perché i valori più grandi sono già in fondo.
  4. if not swapped: break si 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() e list.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

Esegui codice →
main.py
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]))
Crea un pulsante Run per questo esempio

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.

  1. Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
  2. Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
  3. Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Esegui nel compilatore Python →

Errori comuni

Andare un indice troppo in là

result[index + 1] va oltre la fine quando index arriva all'ultima posizione.

Problema
for index in range(len(result)):
    if result[index] > result[index + 1]:
Correzione
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.

Tutte le sfide