¿Cuál es la manera más rápida para ordenar alfabéticamente tu biblioteca? - Chand John

Ver la lección completa en: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john

Trabajas en la biblioteca de la universidad. En medio de una tranquila tarde llegan de repente 1280 libros. Los libros están alineados en línea recta, pero no en orden y el sistema de selección automática no funciona. ¿Cómo organizar los libros de forma rápida? Chand John nos muestra cómo hacerlo, explicando los algoritmos de los que se valen los bibliotecarios y los motores de búsqueda para organizar la información de forma rápida.

Lección de Chand John, animación de Anton Trofimov.

Trabajas en la biblioteca
de la universidad.

En mitad de una tarde tranquila

te llegan de repente unos 1280 libros,

entregados en línea recta
pero desordenados

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

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

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

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

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

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

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

De lo contrario, intercambiarlos.

Hacer lo mismo con el segundo
y el tercero,

repetir el procedimiento

y seguir hasta llegar
al final de la fila.

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

se sigue intercambiándolo
con los libros posteriores

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

Volver a empezar desde el principio
y repetir el mismo procedimiento

para colocar el segundo
en el lugar que le corresponde;

seguir hasta ordenar todos los libros.

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

Es simple pero lento.

En la primera ronda se llegan
a hacer 1279 comparaciones,

luego 1278 y y así sucesivamente,

hasta llegar a un total de 818 560.

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

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

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

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

luego compararlos con el primero
en el primer lugar

y volver a intercambiarlos si hace falta.

Ya se han ordenado los primeros tres.

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

comparando cada uno de ellos
e intercambiando con el de delante

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

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

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

En promedio, creemos que solo
es necesario comparar cada libro

con la mitad de todos
los libros que le preceden.

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

y tardaría cinco días.

Aun así, hay que comparar
demasiados libros.

Te proponemos una idea mejor.

Elegir un libro al azar.

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

Luego, dividir la línea

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

y los otros a la derecha.

Acabas de ahorrarte un montón de tiempo

y sin tener que comparar todos
los libros de la izquierda

con todos que tiene a la derecha.

Ahora, al fijarte
solo en los de la izquierda

vuelve a elegir uno al azar

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

Sigue dividiendo los libros
en base al mismo principio

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

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

Cada ciclo requiere
unas 1280 comparaciones.

Si creaste pilas parecidas

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

tardando 8960 segundos.

Añade 22 segundos para ordenar
estos subconjuntos.

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

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

Pero tiene trampa.

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

pero afortunadamente,
esto ocurre muy de vez en cuando.

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

usada en la actualidad por
los programadores informáticos

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

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

en base a la distancia.

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

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