Algoritmi di ordinamento

Mettere le cose in ordine — nel modo furbo!

Livello Base — linguaggio semplice, senza matematica

Immagina un grosso mazzo di carte numerate, tutte mescolate, e il compito di metterle in ordine dalla più piccola alla più grande. Potresti scorrerle a mano, confrontando e infilando ciascuna al suo posto. Abbastanza facile con dieci carte. Con un milione, lo stesso paziente metodo ti terrebbe occupato per anni.

I computer incontrano questo identico problema tutto il giorno — ordinare le tue email per data, le foto per ora, i risultati di ricerca per pertinenza, i contatti dalla A alla Z. Un algoritmo di ordinamento è solo la precisa ricetta passo-passo che un computer segue per farlo. Ed ecco la cosa su cui vale la pena fermarsi: per lo stessissimo mazzo di carte, alcune ricette sono milioni di volte più veloci di altre.

Il più semplice, il Bubble Sort, percorre la lista confrontando i vicini, scambiando quelli fuori ordine, e ripete finché non resta nulla da scambiare. Funziona, ma è lento — sostanzialmente controlla ogni coppia. L'alternativa furba, il Merge Sort, gioca al divide-et-impera: taglia il mazzo a metà, ordina ciascuna metà, poi ricuce insieme le due metà ordinate. Dividi e fondi, dividi e fondi, e il milione di carte che avrebbe richiesto anni cade in ordine in un batter d'occhio. Stesso compito, strategia selvaggiamente diversa — è tutto qui il gioco.

Complessità Big-O: misurare l'efficienza di un algoritmo

Livello Studente — le equazioni principali

Quanto è buono un algoritmo di ordinamento si riduce a una domanda: man mano che l'input cresce fino a \(n\) elementi, quanto in fretta cresce il lavoro? La notazione Big-O cattura esattamente quel tasso di crescita, nel caso peggiore. Il trucco è che la velocità grezza dipende dal tuo hardware, ma il tasso di crescita è insito nell'algoritmo stesso — ed è il tasso di crescita a decidere chi vince su un milione di elementi.

Il Bubble Sort continua a spazzare la lista, facendo salire i valori grandi verso destra uno scambio alla volta. Per \(n\) elementi sono fino a \(\tfrac{n(n-1)}{2}\) confronti — \(O(n^2)\). Raddoppia l'input e quadruplichi il lavoro. A \(n = 10^6\) sono circa 500 miliardi di confronti, all'incirca 8 minuti su una macchina che ne fa un miliardo al secondo.

Il Merge Sort prende la via del divide-et-impera: dimezza, ordina ricorsivamente ciascuna metà, poi fonde. Ogni fusione è lavoro \(O(n)\) e la ricorsione è profonda solo \(\log_2 n\) livelli, quindi il totale è \(O(n \log n)\). A \(n = 10^6\) sono circa 20 milioni di confronti — qualcosa come 25.000 volte più veloce del Bubble Sort. Il prezzo è la memoria: la fusione richiede \(O(n)\) spazio di appoggio.

Il QuickSort sceglie un pivot, divide l'array in "più piccoli" e "più grandi", e ricorre su ciascun lato. In media è \(O(n \log n)\) con un comportamento della cache delizioso; il suo caso peggiore è \(O(n^2)\) su input già ordinato, domato scegliendo il pivot a caso. I linguaggi reali coprono le scommesse: Python e Java montano il TimSort, un ibrido Merge/Insertion che individua le sequenze già in ordine e sfreccia attraverso dati quasi ordinati in quasi \(O(n)\).

Complessità computazionale, il Teorema Master e le dimostrazioni di limite inferiore

Livello Esperto — profondità matematica completa

01Risolvere le ricorrenze: il Teorema Master

Gli algoritmi divide-et-impera si descrivono con ricorrenze, e la maggior parte rientra in un unico modello: \(T(n) = a\,T(n/b) + f(n)\) — \(a\) sottoproblemi di dimensione \(n/b\), più \(f(n)\) lavoro per dividere e ricombinare. Il Teorema Master legge la risposta confrontando \(f(n)\) con \(n^{\log_b a}\): chi domina vince, e se pareggiano paghi un \(\log n\) extra. Il Merge Sort ha \(a=b=2\) e \(f(n)=\Theta(n)\), che è esattamente il caso di pareggio \(n^{\log_2 2} = n\) — così ne esce \(T(n) = \Theta(n \log n)\), senza alcun giro di parole.

02Il limite inferiore che nessuno può battere

Il Merge Sort è \(O(n\log n)\) — ma qualcosa di più furbo potrebbe essere più veloce? Per qualsiasi ordinamento che funzioni confrontando elementi, la risposta è un netto no, e la dimostrazione è splendida. Modella l'algoritmo come un albero di decisione binario: ogni nodo interno pone un confronto, ogni foglia è una permutazione finita. Ordinare \(n\) elementi significa che l'albero deve avere almeno \(n!\) foglie per distinguere ogni ordinamento, e un albero binario di altezza \(h\) ne ha al più \(2^h\). Quindi \(h \ge \log_2(n!)\), e Stirling lo trasforma in \(\Omega(n \log n)\). Il limite è teorico-informativo — non gli importa quanto sei furbo, solo quanti esiti devi distinguere.

03Battere il limite barando (legalmente)

Quel muro vale solo per gli ordinamenti che confrontano. Esci da lì e puoi andare più veloce sfruttando la struttura nei dati. Il Counting Sort conta gli interi in un intervallo noto \([0,k]\) in \(O(n+k)\); il Radix Sort lo concatena cifra per cifra per \(O(d(n+k))\); il Bucket Sort raggiunge un atteso \(O(n)\) su dati distribuiti uniformemente. Nessuno di questi contraddice il limite inferiore — fanno semplicemente aritmetica sulle chiavi invece di chiedere "quale è più grande?", e il teorema non ha mai promesso nulla al riguardo.

04Il caso medio del QuickSort

Il caso peggiore del QuickSort è un brutto \(O(n^2)\), eppure è l'ordinamento a cui la maggior parte dei sistemi reali ricorre, perché in media non è solo \(O(n\log n)\) ma \(O(n\log n)\) con costanti minuscole e una superba località di cache. La media segue dal sommare le probabilità che due elementi qualsiasi vengano mai confrontati, che porta a \(E[T(n)] = 2n H_n - 2n\) con \(H_n\) il numero armonico — decisamente \(O(n\log n)\). Randomizzare il pivot rende il caso cattivo astronomicamente improbabile anziché semplicemente raro.

05La macchina sotto il modello

Il Big-O conta le operazioni, ma una CPU reale tiene enormemente alla località di memoria — un cache miss può costare centinaia di confronti "gratuiti". È per questo che un algoritmo \(O(n\log n)\) che scorre la memoria in ordine spesso stracci uno teoricamente uguale che salta di qua e di là. Gli algoritmi cache-oblivious (Frigo et al., 1999) sfruttano la ricorsione per raggiungere il comportamento di cache ottimale a ogni dimensione di cache contemporaneamente, senza mai essere informati della dimensione — un promemoria che il modello asintotico è una mappa, non il territorio.

06Il posto dell'ordinamento nello zoo della complessità

L'ordinamento sta comodamente in P, la classe dei problemi risolvibili in tempo polinomiale. Il suo vicino famoso è la domanda se \(P = NP\) — se ogni problema la cui soluzione è rapida da verificare sia anche rapida da risolvere. L'ordinamento è facile; il problema del commesso viaggiatore, che si limita a riordinare città, è NP-difficile e si crede richieda sforzo esponenziale. Un algoritmo ottimale veloce per esso farebbe collassare \(P\) in \(NP\) e porterebbe giù con sé la crittografia moderna. Che un compito tranquillo come mettere le cose in ordine confini con un problema che potrebbe riscrivere la matematica è il dramma silenzioso della teoria della complessità.