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.
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.
current = result[index]🃏 Prendi la carta successivaresult[position] > current👈 La carta a sinistra è più grande?result[position + 1] = result[position]➡️ Fai scorrere la carta più grande di un posto a destraresult[position + 1] = current📥 Lascia cadere la carta nel bucoL'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
for index in range(1, len(result)):parte dal secondo elemento; un elemento da solo è già ordinato.currenttiene il valore da inserire mentre i valori più grandi si spostano.while position >= 0 and result[position] > current:sposta ogni valore più grande di un posto a destra.result[position + 1] = currentlascia 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.insorttrova 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
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]))
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.
- 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
Riscrivere current dentro il ciclo
Il valore va messo una volta, dopo che tutti i valori più grandi si sono spostati.
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
result[position] = current
position -= 1
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