Ordinare dati è una delle operazioni più frequenti in informatica: elenchi di clienti per cognome, ordini per data, risultati di ricerca per pertinenza. Nella pratica quotidiana quasi nessuno scrive un algoritmo di ordinamento da zero, perché ogni linguaggio ne offre uno eccellente. Studiarli resta comunque utile: insegnano idee che ritornano ovunque, come la divisione di un problema in parti, il compromesso tra memoria e velocità, la differenza tra caso medio e caso peggiore.
Insertion sort: l'ordinamento delle carte da gioco
L'insertion sort funziona come chi riordina le carte in mano: prende una carta alla volta e la inserisce nella posizione giusta tra quelle già ordinate.
def insertion_sort(a):
for i in range(1, len(a)):
corrente = a[i]
j = i - 1
while j >= 0 and a[j] > corrente:
a[j + 1] = a[j] # sposta a destra gli elementi maggiori
j -= 1
a[j + 1] = corrente
return a
Nel caso peggiore, un elenco ordinato al contrario, ogni elemento va spostato fino all'inizio: O(n²). Ma su dati quasi ordinati è velocissimo, vicino a O(n), perché ogni elemento si sposta di poco. Per questo, nonostante la sua semplicità, viene usato anche negli algoritmi moderni per gestire i piccoli segmenti.
Merge sort: dividi e conquista
Il merge sort applica una strategia potente: dividere il problema in sottoproblemi più piccoli, risolverli e combinare i risultati.
- Si divide l'elenco a metà.
- Si ordina ciascuna metà, applicando ricorsivamente lo stesso procedimento.
- Si fondono le due metà ordinate in un unico elenco ordinato.
La fusione è il passaggio chiave: date due liste ordinate, basta confrontare ripetutamente i loro primi elementi e prendere il minore.
def merge_sort(a):
if len(a) <= 1:
return a
medio = len(a) // 2
sinistra, destra = merge_sort(a[:medio]), merge_sort(a[medio:])
risultato, i, j = [], 0, 0
while i < len(sinistra) and j < len(destra):
if sinistra[i] <= destra[j]:
risultato.append(sinistra[i]); i += 1
else:
risultato.append(destra[j]); j += 1
return risultato + sinistra[i:] + destra[j:]
Il merge sort è O(n log n) in ogni caso, migliore, medio e peggiore. Il prezzo è la memoria aggiuntiva per le liste temporanee.
Quicksort: veloce in media
Anche il quicksort divide il problema, ma in modo diverso: sceglie un elemento detto pivot e ridistribuisce gli altri in due gruppi, i minori e i maggiori del pivot. Poi ordina ricorsivamente i due gruppi. Non c'è bisogno di una fase di fusione, perché alla fine i gruppi sono già al posto giusto.
In media è O(n log n) e, nelle implementazioni che lavorano direttamente sull'array, molto efficiente nell'uso della memoria. Il suo punto debole è il caso peggiore, O(n²), che si verifica quando il pivot è sistematicamente l'elemento più piccolo o più grande. Un'implementazione ingenua che sceglie sempre il primo elemento cade proprio in questa trappola con dati già ordinati. Le versioni robuste scelgono il pivot in modo casuale o come mediana di alcuni campioni.
Confronto
| Algoritmo | Caso medio | Caso peggiore | Memoria extra | Stabile |
|---|---|---|---|---|
| Insertion sort | O(n²) | O(n²) | O(1) | Sì |
| Merge sort | O(n log n) | O(n log n) | O(n) | Sì |
| Quicksort | O(n log n) | O(n²) | O(log n) tipica | No, nella forma classica |
La stabilità, spesso dimenticata
Un ordinamento è stabile se mantiene l'ordine relativo degli elementi considerati uguali. Sembra un dettaglio, ma ha conseguenze pratiche. Supponi di avere un elenco di ordini già ordinato per data e di volerlo ordinare per cliente: con un algoritmo stabile, gli ordini di ciascun cliente restano in ordine di data. Questo permette di ordinare per più criteri in passaggi successivi, partendo dal criterio meno importante.
Cosa usa davvero il tuo linguaggio
In Python, sorted() e list.sort() usano Timsort, un algoritmo ideato da Tim Peters (affinato nelle versioni più recenti) che combina merge sort e insertion sort, sfruttando le sequenze già ordinate presenti nei dati reali. È stabile e O(n log n) nel caso peggiore. Altri linguaggi usano varianti ibride diverse, spesso con quicksort per i tipi primitivi e algoritmi stabili per gli oggetti.
Nella pratica:
ordini.sort(key=lambda o: o.data) # per data
clienti = sorted(clienti, key=lambda c: (c.cognome, c.nome))
Il parametro key è il modo idiomatico per ordinare oggetti complessi: si indica quale valore confrontare, e si possono usare tuple per più criteri.
Quando scriverne uno
Quasi mai. Le implementazioni delle librerie standard sono state ottimizzate e verificate per anni. Ha senso pensare a un ordinamento personalizzato solo in situazioni particolari: dati che non entrano in memoria e vanno ordinati a blocchi su disco, valori interi in un intervallo ristretto (dove esistono tecniche come il counting sort), o vincoli specifici di sistemi embedded.
In sintesi
- Insertion sort è semplice, O(n²), ma molto veloce su dati quasi ordinati.
- Merge sort divide, ordina e fonde: O(n log n) garantito, al costo di memoria aggiuntiva.
- Quicksort è veloce in media ma va protetto dal caso peggiore con una buona scelta del pivot.
- La stabilità permette di ordinare per più criteri in passaggi successivi.
- Nel lavoro reale usa l'ordinamento della libreria standard con il parametro
key.
