L'ordinamento per fusione (merge sort) in Python
In questa lezione implementerai il merge sort con la strategia divide et impera usando una funzione ricorsiva.
Introduzione
Il problema
Gli ordinamenti semplici rallentano molto quando le liste crescono: raddoppiare i dati quadruplica il lavoro. Il merge sort divide il problema in problemi più piccoli facili da risolvere, e fa crescere il lavoro solo un po' più in fretta dei dati.
Immaginalo così
Il merge sort è come ordinare con degli amici una grande pila di compiti d'esame. Dividi la pila a metà, dai via ogni metà, e loro dividono di nuovo la loro, finché ognuno ha un solo foglio. Poi le coppie di persone uniscono le loro pile ordinate prendendo sempre il foglio in cima più piccolo, finché resta una sola pila ordinata.
if len(values) <= 1:📄 Un foglio solo è già ordinatomerge_sort(values[:middle])✂️ Dividi la pila e ordina ogni metàleft[left_index] <= right[right_index]🤝 Unisci: prendi il foglio in cima più piccoloresult + left[left_index:] + right[right_index:]📚 Aggiungi ciò che resta dell'altra pilaIl merge sort divide una lista a metà, ordina ogni metà in modo ricorsivo e unisce le due metà ordinate, in tempo O(n log n).
Punti chiave
if len(values) <= 1: return valuesè il caso base che ferma la ricorsione.merge_sort(values[:middle])emerge_sort(values[middle:])ordinano le due metà.- Il ciclo
whileprende il valore in testa più piccolo dalefto darightfinché una lista non finisce. left[left_index:]eright[right_index:]aggiungono i valori rimasti, che sono già ordinati.<=prende prima da sinistra in caso di parità, il che tiene i valori uguali nel loro ordine originale.
Quando si usa?
- Ordinare grandi dati in modo prevedibilmente veloce, senza un caso peggiore cattivo.
- Ordinare liste collegate o dati troppo grandi per la memoria (ordinamento esterno).
- Imparare il divide et impera, uno schema usato in molti algoritmi.
Quando non serve
- Codice Python normale:
sorted()usa già Timsort, un mix ottimizzato di merge sort e insertion sort. - Memoria molto scarsa: il merge sort ha bisogno di spazio extra per le liste unite.
Visualizzatore di L'ordinamento per fusione (merge sort) in Python
O(n log n)Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.
Codice di esempio
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
return result + left[left_index:] + right[right_index:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
Risultato dell'esecuzione
[3, 9, 10, 27, 38, 43, 82]
Spiegazione del codice
La funzione ricorsiva divide la lista finché ogni parte ha un solo elemento, perché una lista di un elemento è sempre ordinata. Poi il ciclo while fonde le due sottoliste prendendo sempre l'elemento più piccolo all'inizio di ciascuna. L'algoritmo richiede sempre tempo O(n log n) e O(n) di memoria aggiuntiva.
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
Dimenticare gli avanzi
Quando una metà finisce, il resto dell'altra metà va perso.
return result
return result + left[left_index:] + right[right_index:]
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