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.
No hay comentarios:
Publicar un comentario