L'ordinamento rapido (quick sort) in Python
In questa lezione implementerai il quick sort dividendo la lista attorno a un elemento perno (pivot).
Introduzione
Il problema
Il quicksort è uno degli algoritmi di ordinamento più usati, perché in media è veloce ed è facile da scrivere. Mostra un altro modo di dividere un problema: invece di dividere a metà, divide attorno a un valore scelto.
Immaginalo così
Il quicksort è come ordinare dei libri per altezza attorno a un libro scelto. Metti ogni libro più basso nella pila di sinistra, ogni libro più alto nella pila di destra e quelli della stessa altezza in mezzo. Poi ordini allo stesso modo ogni pila laterale e rimetti insieme le pile.
pivot = values[len(values) // 2]📕 Scegli un libro con cui confrontarelower = [... if value < pivot]⬅️ I libri più bassi a sinistrahigher = [... if value > pivot]➡️ I libri più alti a destraquick_sort(lower) + equal + quick_sort(higher)📚 Ordina ogni lato, poi unisci le pileIl quicksort sceglie un pivot, divide gli altri elementi tra quelli più piccoli e quelli più grandi del pivot, ordina ogni parte in modo ricorsivo e unisce i risultati. In media richiede tempo O(n log n).
Punti chiave
if len(values) <= 1:è il caso base: una lista così è già ordinata.pivot = values[len(values) // 2]prende il valore centrale come pivot.lower,equalehigherdividono i valori attorno al pivot, eequaltiene insieme i duplicati.quick_sort(lower) + equal + quick_sort(higher)ordina i due lati e unisce le tre liste.
Quando si usa?
- Imparare la partizione e la ricorsione.
- Ordinamento generico sul posto in linguaggi e librerie (con una scelta attenta del pivot).
- Problemi di selezione come trovare la mediana (il quickselect usa la stessa partizione).
Quando non serve
- Codice Python normale:
sorted()è più veloce e stabile. - Quando conta un caso peggiore garantito: con pivot scelti male il quicksort diventa
O(n²), il merge sort invece mai.
Visualizzatore di L'ordinamento rapido (quick sort) in Python
O(n log n)Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.
Codice di esempio
def quick_sort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
higher = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(higher)
print(quick_sort([10, 7, 8, 9, 1, 5]))
Risultato dell'esecuzione
[1, 5, 7, 8, 9, 10]
Spiegazione del codice
Questa versione, facile da leggere, sceglie l'elemento centrale come pivot e crea tre liste, lower, equal e higher, con le list comprehension. Il risultato è l'unione di quick_sort(lower), equal e quick_sort(higher). La complessità media è O(n log n), ma con un pivot scelto male può arrivare 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
Perdere i valori uguali al pivot
Con solo < e >, i duplicati del pivot spariscono.
return quick_sort(lower) + [pivot] + quick_sort(higher)
return quick_sort(lower) + equal + quick_sort(higher)
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