Algoritmi Python

L'ordinamento per inserimento (insertion sort) in Python

In questa lezione implementerai l'insertion sort inserendo ogni elemento nella posizione corretta della parte già ordinata.

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

Introduzione

Il problema

I dati arrivano spesso quasi ordinati, o un elemento alla volta: una lista ordinata di punteggi riceve un nuovo punteggio. Riordinare tutto è uno spreco. L'insertion sort gestisce molto bene questo caso ed è il modo in cui molte persone ordinano le carte a mano.

Immaginalo così

L'insertion sort è il modo in cui ordini le carte in mano. Prendi una carta alla volta e la fai scorrere a sinistra oltre ogni carta più grande finché non sta al posto giusto. Le carte alla sua sinistra sono sempre in ordine.

Dall'ordinare le carte al codice
current = result[index]🃏 Prendi la carta successiva
result[position] > current👈 La carta a sinistra è più grande?
result[position + 1] = result[position]➡️ Fai scorrere la carta più grande di un posto a destra
result[position + 1] = current📥 Lascia cadere la carta nel buco
La parte sinistra è sempre ordinata; ogni nuovo elemento ci viene inserito.
In una frase

L'insertion sort costruisce una parte ordinata un elemento alla volta spostando a destra gli elementi più grandi e inserendo l'elemento attuale nel buco; è O(n²) nel caso peggiore ma vicino a O(n) su dati quasi ordinati.

Punti chiave

  1. for index in range(1, len(result)): parte dal secondo elemento; un elemento da solo è già ordinato.
  2. current tiene il valore da inserire mentre i valori più grandi si spostano.
  3. while position >= 0 and result[position] > current: sposta ogni valore più grande di un posto a destra.
  4. result[position + 1] = current lascia cadere il valore nel buco che si è aperto.

Quando si usa?

  • Liste piccole o quasi ordinate.
  • Tenere una lista ordinata mentre arrivano nuovi elementi.
  • Come passo finale dentro ordinamenti più veloci, che passano all'insertion sort per i pezzi piccoli.

Quando non serve

  • Liste grandi e casuali: gli spostamenti diventano lenti, quindi usa sorted().
  • Inserire spesso in una grande lista ordinata: bisect.insort trova la posizione con la ricerca binaria.

Visualizzatore di L'ordinamento per inserimento (insertion 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 insertion_sort(values):
    result = values.copy()
    for index in range(1, len(result)):
        current = result[index]
        position = index - 1
        while position >= 0 and result[position] > current:
            result[position + 1] = result[position]
            position -= 1
        result[position + 1] = current
    return result

print(insertion_sort([9, 5, 1, 4, 3]))
Crea un pulsante Run per questo esempio

Risultato dell'esecuzione

[1, 3, 4, 5, 9]

Spiegazione del codice

La variabile current contiene il valore da inserire. Il ciclo while sposta di una posizione a destra i valori maggiori di current per fare spazio, poi current viene messo in quel posto. Nel caso peggiore la complessità è O(n²), ma con dati quasi ordinati l'algoritmo si avvicina a O(n).

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

Riscrivere current dentro il ciclo

Il valore va messo una volta, dopo che tutti i valori più grandi si sono spostati.

Problema
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    result[position] = current
    position -= 1
Correzione
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    position -= 1
result[position + 1] = current

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