Tu lavori nella biblioteca universitaria.
Sei nel bel mezzo di un placido pomeriggio
quando all'improvviso arriva un carico di 1.280 libri diversi.
I libri sono stati consegnati in una singola, lunga fila,
ma sono tutti in disordine,
e il sistema di classificazione automatica è rotto.
Come se non bastasse, le lezioni ricominciano domani,
il che vuol dire che di prima mattina
gli studenti si presenteranno in massa alla ricerca dei loro libri.
Come puoi catalogarli tutti in tempo?
Un modo sarebbe cominciare da un capo della fila con il primo paio di libri.
Se i primi due sono in ordine, lasciali come sono.
Altrimenti, scambiali.
Poi guarda il secondo e il terzo libro,
ripeti il procedimento
e continua fino alla fine della linea.
Ad un certo punto arriverai a quello che dovrebbe essere l'ultimo,
continua a scambiarlo con i libri seguenti,
facendolo scorrere finché non raggiunge la fine, il suo posto.
Poi, comincia dall'inizio e ripeti il procedimento
per mettere a posto il penultimo libro,
e continua finché tutti i libri non sono catalogati.
Questo metodo si chiama Bubble Sort.
È semplice ma lento.
Dovresti fare 1.279 confronti nel primo giro,
poi 1,278 e così via,
per un totale di 818.560 confronti.
Se ogni confronto durasse un secondo, l'intero processo durerebbe nove giorni.
Una seconda strategia sarebbe di iniziare a catalogare solo i primi due libri.
Poi prendi il terzo libro e lo confronti con il libro al secondo posto.
Se deve stare prima del secondo, scambiali,
poi confrontalo con il libro al primo posto
e scambiali di nuovo se necessario.
Ora hai catalogato i primi tre libri.
Prosegui aggiungendo un libro alla volta alla pila già catalogata,
confrontando e scambiando il nuovo libro con quello che lo precede
finché non si trova al posto giusto tra i libri finora catalogati.
Questo si chiama Insertion Sort.
A differenza del Bubble Sort, non bisogna confrontare ciascun paio di libri.
In media, dovremmo solo confrontare ogni libro
con la metà dei libri che lo precedono.
In questo caso, il numero totale di confronti
sarebbe 409.280,
e richiederebbe quasi cinque giorni.
Stiamo facendo ancora troppi confronti.
Ecco un'idea migliore.
Prendi un libro a caso.
Questo è il divisorio e lo confronterai con ogni altro libro.
Poi, dividi la fila
mettendo tutti i libri prima del divisorio a sinistra
e quello dopo a destra.
Hai appena risparmiato un sacco di tempo
non confrontando nessun libro a sinistra
con quelli della destra.
Guardando i libri sulla sinistra,
scegli un altro libro divisorio a caso
e separa i libri che vengono prima da quelli che vengono dopo.
Continua a creare sotto-divisori così
finché non hai tante mini pile di libri,
ognuna delle quali puoi catalogare con un'altra strategia, come l'Insertion.
Ogni ciclo di ripartizioni richiede circa 1.280 confronti.
Se i divisori sono ben equilibrati,
dividere i libri in 128 file di dieci richiederebbe sette cicli,
o 8.960 secondi.
Catalogare queste sotto-file richiederebbe 22 secondi circa.
In tutto, questo metodo, conosciuto come QuickSort,
potrebbe catalogare i libri in meno di tre ore e mezza.
Ma c'è un inghippo.
I divisori possono essere sbilanciati e non ti farebbero risparmiare tempo.
Per fortuna, accade raramente.
Ecco perché QuickSort è una della strategie più efficaci
usata oggi dai programmatori di computer.
È usata ad esempio nei negozi online per catalogare oggetti in base al prezzo,
o per elencare i benzinai vicini ad un dato luogo
in base alla distanza.
Nel tuo caso, hai finito la catalogazione in men che non si dica.
Un'altra giornata da brividi in biblioteca.