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

Traductor: Denise RQ Revisor: Sebastian Betti

You work at the college library.

Trabajas en la biblioteca de la universidad.

You're in the middle of a quiet afternoon

En mitad de una tarde tranquila

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

te llegan de repente unos 1280 libros,

entregados en línea recta pero desordenados

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

but they're all out of order,

and the automatic sorting system is broken.

y el sistema de clasificación automática no funciona.

Además, mañana comienzan las clases de nuevo,

To make matters worse, classes start tomorrow,

which means that first thing in the morning,

lo que significa que a primera hora de la mañana

students will show up in droves looking for these books.

todos los estudiantes se presentarán en la biblioteca buscando sus libros.

How can you get them all sorted in time?

¿Cómo se pueden ordenar todos los libros a tiempo?

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

Una forma sería comenzar por el primer par de libros en un extremo de la fila

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

y si los dos primeros están en orden, dejarlos como están.

Otherwise, swap them.

De lo contrario, intercambiarlos.

Then, look at the second and third books,

Hacer lo mismo con el segundo y el tercero,

repeat the process,

repetir el procedimiento

and continue until you reach the end of the line.

y seguir hasta llegar al final de la fila.

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

En un momento dado, se encuentra el libro que debe ser el último,

se sigue intercambiándolo con los libros posteriores

and keep swapping it with every subsequent book,

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

desplazándolo a lo largo de la fila hasta que llegue al final.

Then, start from the beginning and repeat the process

Volver a empezar desde el principio y repetir el mismo procedimiento

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

para colocar el segundo en el lugar que le corresponde;

and keep going until all books are sorted.

seguir hasta ordenar todos los libros.

This approach is called Bubble Sort.

Este proceso se llama el método de la burbuja.

It's simple but slow.

Es simple pero lento.

En la primera ronda se llegan a hacer 1279 comparaciones,

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

then 1,278, and so on,

luego 1278 y y así sucesivamente,

adding up to 818,560 comparisons.

hasta llegar a un total de 818 560.

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

Si cada comparación dura un segundo, harían falta nueve días.

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

Una segunda técnica implica empezar con solo los primeros 2 libros

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

para luego comparar el tercer libro con el que se encuentra en el segundo lugar.

If it belongs before the second book, swap them,

Si le corresponde colocarlo delante de este segundo libro, intercambiarlos,

then compare it with the book in the first spot,

luego compararlos con el primero en el primer lugar

and swap again if needed.

y volver a intercambiarlos si hace falta.

Now you've sorted the first three books.

Ya se han ordenado los primeros tres.

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

Seguir con un libro a la vez, ordenándolos por conjuntos,

comparing and swapping the new book with the one before it

comparando cada uno de ellos e intercambiando con el de delante

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

hasta encontrar el lugar que le corresponde entre los ya ordenados.

Esto se denomina la técnica por inserción.

This is called Insertion Sort.

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

A diferencia del método de la burbuja, no requiere comparar cada par.

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

En promedio, creemos que solo es necesario comparar cada libro

to half of the books that came before it.

con la mitad de todos los libros que le preceden.

In that case, the total number of comparisons

En este caso el número total de comparaciones será 409 280

would be 409,280,

taking almost five days.

y tardaría cinco días.

Aun así, hay que comparar demasiados libros.

You're still doing way too many comparisons.

Here's a better idea.

Te proponemos una idea mejor.

First, pick a random book.

Elegir un libro al azar.

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

Usarlo de separador y luego compararlo con todos los otros libros.

Then, divide the line

Luego, dividir la línea

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

y colocar todos los libros de antes de la separación a la izquierda

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

y los otros a la derecha.

You've just saved loads of time

Acabas de ahorrarte un montón de tiempo

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

y sin tener que comparar todos los libros de la izquierda

to any of the ones on the right ever again.

con todos que tiene a la derecha.

Now, looking only at the books on the left,

Ahora, al fijarte solo en los de la izquierda

you can again pick a random partition book

vuelve a elegir uno al azar

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

y separa los libros de delante y detrás de ese en dos grupos.

You can keep creating sub-partitions like this

Sigue dividiendo los libros en base al mismo principio

until you have a bunch of small sub-lines,

hasta que llegues a tener pequeñas pilas de libros,

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

listas para ordenarlas en base al método de inserción.

Each round of partitioning requires about 1,280 comparisons.

Cada ciclo requiere unas 1280 comparaciones.

If your partitions are pretty balanced,

Si creaste pilas parecidas

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

deberías tener 128 pilas, con 10 libros en cada grupo,

tardando 8960 segundos.

or 8,960 seconds.

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

Añade 22 segundos para ordenar estos subconjuntos.

All in all, this method known as QuickSort

Con esta técnica llamada catalogación rápida

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

puedes llegar a ordenar tus libros en menos de una hora y media.

But there's a catch.

Pero tiene trampa.

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

Si los subconjuntos están desproporcionados perderás mucho tiempo

pero afortunadamente, esto ocurre muy de vez en cuando.

Luckily, this rarely happens.

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

Esta técnica es una de las más eficientes

used by programmers today.

usada en la actualidad por los programadores informáticos

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

por ejemplo en las tiendas en línea para categorizar elementos, según el precio

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

o crear una lista de todas las gasolineras más cercanas a un lugar determinado,

sorted by distance.

en base a la distancia.

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

En este caso, la catalogación está resuelta y queda tiempo de sobra.

Just another high-stakes day in the library.

Y aquí va otro día crucial en la biblioteca.