Quick Sort, l’arte di dividere per conquistare
Dopo aver esplorato l’assurdo universo del Bogosort — che fondamentalmente si affida al caos sperando nel miracolo — oggi facciamo un salto dall’altra parte dello spettro. Parliamo del Quick Sort, un algoritmo che ha rivoluzionato il modo di ordinare le cose… con intelligenza.
Quick Sort è un algoritmo di ordinamento ricorsivo basato sulla strategia del “divide et impera”. Inventato da Tony Hoare nel 1959 (sì, prima ancora che esistessero i personal computer), è ancora oggi tra gli algoritmi più usati per ordinare liste, vettori e dataset.
l Quick Sort è veloce nella media. In condizioni normali ha una complessità di O(n log n), ed è in genere più efficiente di algoritmi più “meccanici” come il Merge Sort, perché richiede meno memoria ausiliaria e si comporta bene anche su grandi volumi di dati.
Se il Bogosort è l’algoritmo dell’anarchia, il Quick Sort è il generale stratega. Divide il problema, lo affronta con metodo e precisione, e lo risolve con sorprendente rapidità. Un perfetto esempio di come “veloce” non significhi “superficiale”, ma strategico.
Nota tecnica: nel caso peggiore (pivot scelto male), può scendere a O(n²), ma questo si può mitigare con buone strategie di scelta del pivot (come il “median-of-three”).
L’idea di base è elegante quanto potente:
Scegli un pivot (un elemento qualunque dalla lista).
Dividi il resto della lista in due sottoliste:
Tutti gli elementi minori del pivot.
Tutti gli elementi maggiori (o uguali).
Applica ricorsivamente il Quick Sort alle due sottoliste.
Unisci i risultati:
[ordina(minori)] + [pivot] + [ordina(maggiori)]
Come si sceglie il pivot?
La scelta del pivot nel Quick Sort è un passaggio cruciale, perché da essa dipende in gran parte l’efficienza dell’algoritmo. Il pivot è l’elemento della lista rispetto al quale dividiamo tutti gli altri: quelli più piccoli andranno da una parte, quelli più grandi dall’altra. Dopo la divisione e l’ordinamento ricorsivo delle sottoliste, il pivot finirà nella sua posizione definitiva nella lista ordinata.
Ma come si sceglie il pivot?
Ci sono diversi approcci, ognuno con vantaggi e svantaggi. In genere, deve essere un algoritmo semplice e veloce da implementare, per non far perdere la velocità che caratterizza il quick sort stesso.
1. Primo elemento
pivot = lista[0]
- ✅ Semplice e veloce.
- ❌ Rischioso su liste già ordinate: può causare il caso peggiore O(n²).
2. Ultimo elemento
pivot = lista[-1]
- ✅ Facile da implementare.
- ❌ Stessi problemi del primo elemento se la lista è ordinata al contrario.
3. Elemento casuale
import random
pivot = random.choice(lista)
- ✅ Riduce il rischio di pessime partizioni.
- ❌ Richiede un generatore di numeri casuali, quindi può essere un po’ più lento.
4. Mediana di tre (median-of-three)
a = lista[0]
b = lista[len(lista)//2]
c = lista[-1]
pivot = sorted([a, b, c])[1] # la mediana tra primo, centrale e ultimo
- ✅ Ottimo compromesso tra efficienza e stabilità.
- ✅ Aiuta a evitare il caso peggiore anche su liste parzialmente ordinate.
- ❌ Leggermente più complesso da implementare.
Quale conviene?
Dipende dal contesto:
- In esercizi didattici o script semplici: primo o ultimo elemento va bene.
- In applicazioni serie o dati potenzialmente problematici: pivot casuale o mediana di tre è preferibile.
- In librerie standard (come in Python): si usa un algoritmo ibrido (es. Timsort) che evita del tutto i peggiori casi del Quick Sort.
Un esempio pratico
Ordinare la lista:[6, 3, 8, 5, 2]
Scegliamo il pivot: elemento 5
Dividiamo:
Minori:
[3, 2]Maggiori:
[6, 8]
Ordiniamo ricorsivamente:
[3, 2]→ pivot: 2 →[ ] + [2] + [3]→[2, 3][6, 8]→ pivot: 6 →[ ] + [6] + [8]→[6, 8]
Ricomponiamo:
[2, 3] + [5] + [6, 8]→ [2, 3, 5, 6, 8]
Altro esempio pratico
Lista: [9, 1, 5, 3, 7]
- Primo elemento: pivot = 9
- Ultimo elemento: pivot = 7
- Random: pivot = (mettiamo) 3
- Mediana di tre: tra
9,5,7→ mediana è 7
