What's the fastest way to alphabetize your bookshelf? - Chand John

Qual è il modo più veloce per catalogare la tua libreria? - Chand John

Traduttore: Silvia Elisabetta La Penna Revisore: Federico MINELLE

You work at the college library.

Tu lavori nella biblioteca universitaria.

You're in the middle of a quiet afternoon

Sei nel bel mezzo di un placido pomeriggio

when suddenly a shipment of 1,280 different books arrives.

quando all'improvviso arriva un carico di 1.280 libri diversi.

The books have been dropped of in one long straight line,

I libri sono stati consegnati in una singola, lunga fila,

but they're all out of order,

ma sono tutti in disordine,

and the automatic sorting system is broken.

e il sistema di classificazione automatica è rotto.

To make matters worse, classes start tomorrow,

Come se non bastasse, le lezioni ricominciano domani,

which means that first thing in the morning,

il che vuol dire che di prima mattina

students will show up in droves looking for these books.

gli studenti si presenteranno in massa alla ricerca dei loro libri.

How can you get them all sorted in time?

Come puoi catalogarli tutti in tempo?

One way would be to start at one end of the line with the first pair of books.

Un modo sarebbe cominciare da un capo della fila con il primo paio di libri.

If the first two books are in order, then leave them as they are.

Se i primi due sono in ordine, lasciali come sono.

Otherwise, swap them.

Altrimenti, scambiali.

Then, look at the second and third books,

Poi guarda il secondo e il terzo libro,

repeat the process,

ripeti il procedimento

and continue until you reach the end of the line.

e continua fino alla fine della linea.

At some point, you'll come across the book that should be last,

Ad un certo punto arriverai a quello che dovrebbe essere l'ultimo,

and keep swapping it with every subsequent book,

continua a scambiarlo con i libri seguenti,

moving it down the line until it reaches the end where it belongs.

facendolo scorrere finché non raggiunge la fine, il suo posto.

Then, start from the beginning and repeat the process

Poi, comincia dall'inizio e ripeti il procedimento

to get the second to last book in its proper place,

per mettere a posto il penultimo libro,

and keep going until all books are sorted.

e continua finché tutti i libri non sono catalogati.

This approach is called Bubble Sort.

Questo metodo si chiama Bubble Sort.

It's simple but slow.

È semplice ma lento.

You'd make 1,279 comparisons in the first round,

Dovresti fare 1.279 confronti nel primo giro,

then 1,278, and so on,

poi 1,278 e così via,

adding up to 818,560 comparisons.

per un totale di 818.560 confronti.

If each took just one second, the process would take over nine days.

Se ogni confronto durasse un secondo, l'intero processo durerebbe nove giorni.

A second strategy would be to start by sorting just the first two books.

Una seconda strategia sarebbe di iniziare a catalogare solo i primi due libri.

Then, take the third book and compare it with the book in the second spot.

Poi prendi il terzo libro e lo confronti con il libro al secondo posto.

If it belongs before the second book, swap them,

Se deve stare prima del secondo, scambiali,

then compare it with the book in the first spot,

poi confrontalo con il libro al primo posto

and swap again if needed.

e scambiali di nuovo se necessario.

Now you've sorted the first three books.

Ora hai catalogato i primi tre libri.

Keep adding one book at a time to the sorted sub-line,

Prosegui aggiungendo un libro alla volta alla pila già catalogata,

comparing and swapping the new book with the one before it

confrontando e scambiando il nuovo libro con quello che lo precede

until it's correctly placed among the books sorted so far.

finché non si trova al posto giusto tra i libri finora catalogati.

This is called Insertion Sort.

Questo si chiama Insertion Sort.

Unlike Bubble Sort, it usually doesn't require comparing every pair of books.

A differenza del Bubble Sort, non bisogna confrontare ciascun paio di libri.

On average, we'd expect to only need to compare each book

In media, dovremmo solo confrontare ogni libro

to half of the books that came before it.

con la metà dei libri che lo precedono.

In that case, the total number of comparisons

In questo caso, il numero totale di confronti

would be 409,280,

sarebbe 409.280,

taking almost five days.

e richiederebbe quasi cinque giorni.

You're still doing way too many comparisons.

Stiamo facendo ancora troppi confronti.

Here's a better idea.

Ecco un'idea migliore.

First, pick a random book.

Prendi un libro a caso.

Call it the partition and compare it to every other book.

Questo è il divisorio e lo confronterai con ogni altro libro.

Then, divide the line

Poi, dividi la fila

by placing all the books that come before the partition on its left

mettendo tutti i libri prima del divisorio a sinistra

and all the ones that come after it on its right.

e quello dopo a destra.

You've just saved loads of time

Hai appena risparmiato un sacco di tempo

by not having to compare any of the books on the left

non confrontando nessun libro a sinistra

to any of the ones on the right ever again.

con quelli della destra.

Now, looking only at the books on the left,

Guardando i libri sulla sinistra,

you can again pick a random partition book

scegli un altro libro divisorio a caso

and separate those books that come before it from those that come after it.

e separa i libri che vengono prima da quelli che vengono dopo.

You can keep creating sub-partitions like this

Continua a creare sotto-divisori così

until you have a bunch of small sub-lines,

finché non hai tante mini pile di libri,

each of which you'd sort quickly using another strategy, like Insertion Sort.

ognuna delle quali puoi catalogare con un'altra strategia, come l'Insertion.

Each round of partitioning requires about 1,280 comparisons.

Ogni ciclo di ripartizioni richiede circa 1.280 confronti.

If your partitions are pretty balanced,

Se i divisori sono ben equilibrati,

dividing the books into 128 sub-lines of ten would take about seven rounds,

dividere i libri in 128 file di dieci richiederebbe sette cicli,

or 8,960 seconds.

o 8.960 secondi.

Sorting these sub-lines would add about 22 seconds each.

Catalogare queste sotto-file richiederebbe 22 secondi circa.

All in all, this method known as QuickSort

In tutto, questo metodo, conosciuto come QuickSort,

could sort the books in under three and a half hours.

potrebbe catalogare i libri in meno di tre ore e mezza.

But there's a catch.

Ma c'è un inghippo.

Your partitions could end up lopsided, saving no time at all.

I divisori possono essere sbilanciati e non ti farebbero risparmiare tempo.

Luckily, this rarely happens.

Per fortuna, accade raramente.

That's why QuickSort is one of the most efficient strategies

Ecco perché QuickSort è una della strategie più efficaci

used by programmers today.

usata oggi dai programmatori di computer.

They use it for things like sorting items in an online store by price,

È usata ad esempio nei negozi online per catalogare oggetti in base al prezzo,

or creating a list of all the gas stations close to a given location

o per elencare i benzinai vicini ad un dato luogo

sorted by distance.

in base alla distanza.

In your case, you're done quick sorting with time to spare.

Nel tuo caso, hai finito la catalogazione in men che non si dica.

Just another high-stakes day in the library.

Un'altra giornata da brividi in biblioteca.