WEBVTT
00:00:06.911 --> 00:00:09.177
Tu lavori nella biblioteca universitaria.
00:00:09.177 --> 00:00:11.397
Sei nel bel mezzo di un placido pomeriggio
00:00:11.397 --> 00:00:18.011
quando all'improvviso arriva un carico
di 1.280 libri diversi.
00:00:18.011 --> 00:00:21.690
I libri sono stati consegnati
in una singola, lunga fila,
00:00:21.690 --> 00:00:23.288
ma sono tutti in disordine,
00:00:23.288 --> 00:00:27.031
e il sistema di classificazione
automatica è rotto.
00:00:27.031 --> 00:00:29.667
Come se non bastasse,
le lezioni ricominciano domani,
00:00:29.667 --> 00:00:32.005
il che vuol dire che di prima mattina
00:00:32.005 --> 00:00:36.557
gli studenti si presenteranno in massa
alla ricerca dei loro libri.
00:00:36.557 --> 00:00:39.493
Come puoi catalogarli tutti in tempo?
00:00:39.493 --> 00:00:44.779
Un modo sarebbe cominciare da un capo
della fila con il primo paio di libri.
00:00:44.779 --> 00:00:48.626
Se i primi due sono in ordine,
lasciali come sono.
00:00:48.626 --> 00:00:50.920
Altrimenti, scambiali.
00:00:50.920 --> 00:00:53.216
Poi guarda il secondo e il terzo libro,
00:00:53.216 --> 00:00:54.879
ripeti il procedimento
00:00:54.879 --> 00:00:57.935
e continua fino alla fine della linea.
00:00:57.935 --> 00:01:01.185
Ad un certo punto arriverai
a quello che dovrebbe essere l'ultimo,
00:01:01.185 --> 00:01:04.710
continua a scambiarlo
con i libri seguenti,
00:01:04.710 --> 00:01:09.280
facendolo scorrere finché non raggiunge
la fine, il suo posto.
00:01:09.280 --> 00:01:12.225
Poi, comincia dall'inizio
e ripeti il procedimento
00:01:12.225 --> 00:01:15.510
per mettere a posto
il penultimo libro,
00:01:15.510 --> 00:01:18.821
e continua finché tutti i libri
non sono catalogati.
00:01:18.821 --> 00:01:21.862
Questo metodo si chiama Bubble Sort.
00:01:21.862 --> 00:01:24.156
È semplice ma lento.
00:01:24.156 --> 00:01:29.331
Dovresti fare 1.279 confronti
nel primo giro,
00:01:29.331 --> 00:01:33.623
poi 1,278 e così via,
00:01:33.623 --> 00:01:38.542
per un totale di 818.560 confronti.
00:01:38.542 --> 00:01:44.273
Se ogni confronto durasse un secondo,
l'intero processo durerebbe nove giorni.
00:01:44.273 --> 00:01:48.569
Una seconda strategia sarebbe di iniziare
a catalogare solo i primi due libri.
00:01:48.569 --> 00:01:53.733
Poi prendi il terzo libro e lo confronti
con il libro al secondo posto.
00:01:53.733 --> 00:01:57.173
Se deve stare prima del secondo,
scambiali,
00:01:57.173 --> 00:01:59.641
poi confrontalo
con il libro al primo posto
00:01:59.641 --> 00:02:01.682
e scambiali di nuovo se necessario.
00:02:01.682 --> 00:02:03.880
Ora hai catalogato i primi tre libri.
00:02:03.880 --> 00:02:07.732
Prosegui aggiungendo un libro alla volta
alla pila già catalogata,
00:02:07.732 --> 00:02:11.809
confrontando e scambiando il nuovo libro
con quello che lo precede
00:02:11.809 --> 00:02:16.004
finché non si trova al posto giusto
tra i libri finora catalogati.
00:02:16.004 --> 00:02:18.213
Questo si chiama Insertion Sort.
00:02:18.213 --> 00:02:22.944
A differenza del Bubble Sort, non bisogna
confrontare ciascun paio di libri.
00:02:22.944 --> 00:02:26.954
In media, dovremmo solo
confrontare ogni libro
00:02:26.954 --> 00:02:29.414
con la metà dei libri che lo precedono.
00:02:29.414 --> 00:02:32.123
In questo caso,
il numero totale di confronti
00:02:32.123 --> 00:02:35.983
sarebbe 409.280,
00:02:35.983 --> 00:02:38.135
e richiederebbe quasi cinque giorni.
00:02:38.135 --> 00:02:40.624
Stiamo facendo ancora troppi confronti.
00:02:40.624 --> 00:02:42.515
Ecco un'idea migliore.
00:02:42.515 --> 00:02:44.885
Prendi un libro a caso.
00:02:44.885 --> 00:02:49.606
Questo è il divisorio
e lo confronterai con ogni altro libro.
00:02:49.606 --> 00:02:51.515
Poi, dividi la fila
00:02:51.515 --> 00:02:55.666
mettendo tutti i libri
prima del divisorio a sinistra
00:02:55.666 --> 00:02:58.825
e quello dopo a destra.
00:02:58.825 --> 00:03:00.415
Hai appena risparmiato
un sacco di tempo
00:03:00.415 --> 00:03:03.845
non confrontando
nessun libro a sinistra
00:03:03.845 --> 00:03:07.245
con quelli della destra.
00:03:07.245 --> 00:03:09.665
Guardando i libri sulla sinistra,
00:03:09.665 --> 00:03:12.542
scegli un altro libro divisorio a caso
00:03:12.542 --> 00:03:17.266
e separa i libri che vengono prima
da quelli che vengono dopo.
00:03:17.266 --> 00:03:19.736
Continua a creare sotto-divisori così
00:03:19.736 --> 00:03:22.384
finché non hai tante mini pile di libri,
00:03:22.384 --> 00:03:27.764
ognuna delle quali puoi catalogare
con un'altra strategia, come l'Insertion.
00:03:27.764 --> 00:03:32.926
Ogni ciclo di ripartizioni richiede
circa 1.280 confronti.
00:03:32.926 --> 00:03:35.466
Se i divisori sono ben equilibrati,
00:03:35.466 --> 00:03:41.256
dividere i libri in 128 file di dieci
richiederebbe sette cicli,
00:03:41.256 --> 00:03:43.947
o 8.960 secondi.
00:03:43.947 --> 00:03:48.736
Catalogare queste sotto-file
richiederebbe 22 secondi circa.
00:03:48.736 --> 00:03:51.817
In tutto, questo metodo,
conosciuto come QuickSort,
00:03:51.817 --> 00:03:54.883
potrebbe catalogare i libri
in meno di tre ore e mezza.
00:03:54.883 --> 00:03:55.997
Ma c'è un inghippo.
00:03:55.997 --> 00:03:59.575
I divisori possono essere sbilanciati
e non ti farebbero risparmiare tempo.
00:03:59.575 --> 00:04:01.477
Per fortuna, accade raramente.
00:04:01.477 --> 00:04:04.910
Ecco perché QuickSort
è una della strategie più efficaci
00:04:04.910 --> 00:04:06.916
usata oggi dai programmatori di computer.
00:04:06.916 --> 00:04:10.847
È usata ad esempio nei negozi online
per catalogare oggetti in base al prezzo,
00:04:10.847 --> 00:04:14.858
o per elencare i benzinai
vicini ad un dato luogo
00:04:14.858 --> 00:04:16.379
in base alla distanza.
00:04:16.379 --> 00:04:20.407
Nel tuo caso, hai finito
la catalogazione in men che non si dica.
00:04:20.407 --> 00:04:22.668
Un'altra giornata
da brividi in biblioteca.