Algoritmi Python

L'ordinamento rapido (quick sort) in Python

In questa lezione implementerai il quick sort dividendo la lista attorno a un elemento perno (pivot).

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

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.

Dalle pile di libri al codice
pivot = values[len(values) // 2]📕 Scegli un libro con cui confrontare
lower = [... if value < pivot]⬅️ I libri più bassi a sinistra
higher = [... if value > pivot]➡️ I libri più alti a destra
quick_sort(lower) + equal + quick_sort(higher)📚 Ordina ogni lato, poi unisci le pile
Partiziona attorno a un pivot, poi ordina ogni lato allo stesso modo.
In una frase

Il 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

  1. if len(values) <= 1: è il caso base: una lista così è già ordinata.
  2. pivot = values[len(values) // 2] prende il valore centrale come pivot.
  3. lower, equal e higher dividono i valori attorno al pivot, e equal tiene insieme i duplicati.
  4. 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

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

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.

  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

Perdere i valori uguali al pivot

Con solo < e >, i duplicati del pivot spariscono.

Problema
return quick_sort(lower) + [pivot] + quick_sort(higher)
Correzione
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