Trabajas en la biblioteca de una universidad. Es una tranquila tarde cuando, de repente, llega un cargamento de 1280 libros. Los libros, en línea recta, están completamente desordenados, y la máquina automática encargada de la labor de ordenación está estropeada. ¿Cuál sería la forma más rápida de ordenarlos? El vídeo es, en realidad, una metáfora para hablar de forma educativa sobre la eficiencia de diferentes algoritmos de ordenación, algo comúnmente utilizado en diversas tareas de programación informática para todo tipo de situaciones.
![La forma más rápida de ordenar alfabéticamente una librería (una metáfora sobre algoritmos de ordenación) [ENG]](https://cdn.mnmstatic.net/cache/29/40/media_thumb_2x-link-2703476.jpeg?1480493287)
Comentarios
O sea, lo que cualquier programador sabe: quicksort. El problema es que a veces no es tan fácil en el mundo físico.
Por ejemplo, para ordenar un grupo de 200 exámenes, como le pasaba a mi cuñao: tienes que mover las manos y buscar el nombre del alumno, descifrarlo, desplazarlo físicamente a su lugar, hojear y hojear y desplazarte a través de los 200 exámenes usando las manos... No, no es un "array" en memoria RAM.
Al final lo que hacía era dividir el abecedario en tres grupos: [a-i], [j-p], [q-z] o similares; clasificar cada examen en su grupo (sobre una mesa) y después ordenar a mano (pseudo-quicksort) cada uno de esos grupos, ya mucho más manejables.
Variaciones: dividir el abecedario en 4, 5 ó 6 grupos, aplicar luego el mismo proceso a cada uno de los grupos (si alguno sigue siendo grande), etc.
Seguro que hay algún método más eficiente, pero éste no funcionaba mal.
#14 Siempre puede tirarlos al aire y suspender a todos.
#19 al menos usar la técnica del paraguas, ¿no? Alguna merecerá la pena.
#14 se parece a la optimización del quicksort usando un insertionsort, de hecho es así como se optimiza. Es una pregunta típica de examen de programación
Cc #16 #23
#14 En Stack Overflow hay una pregunta sobre cómo emparejar calcetines.
Las mejores respuestas veían puntos como los que tu notas: el cerebro y nuestro sistema de visión no son máquinas. Pero también podemos aplicar algoritmos que sean más eficiente en ellos.
Editado: es esta: http://stackoverflow.com/questions/14415881/how-to-pair-socks-from-a-pile-efficiently
conozco una persona que estuvo muchos años atrás haciendo una especie de prácticas en una residencia de abuelos, y cuando llegó le indicaron que ordenase la sala de biblioteca ya que tenían problemas para encontrar los libros, resulta que hasta el momento los tenían ordenados por tamaño... suerte aún que las enciclopedias por esa misma razón estaban los tomos unos al lado de otros...
#8 AUnque te parezca mentira, el sistema de tamaños es un sistema que se utiliza profesionalmente en bibliotecas. En este caso, es obvio que no. Pero suele ser un sistema de ordenación secundaria utilizado en depósitos ordenados primariamente por número currens -Un libro tras otro dandole un número correlativo-.
#8 dafac?
Ojo, si se hace mal; el autor más prolifico de la biblioteca es un tal "anonimo"
#11 Seguido muy de cerca por Kim Jong Il
#10 Esa máquina coloca libros ya clasificados, que no es el caso de ordenar nuevos libros. Tampoco los ordena alfabéticamente.
¿la máquina automática encargada de la labor de ordenación está estropeada? ¿Qué máquina es esa?
#1 Además, el tema es recurrente:
https://www.meneame.net/search?q=algoritmo ordenacion
#7
#7 #1 Además, el tema es recurrente:
www.meneame.net/search?q=algoritmo ordenacion
#35 #7 #1 Además, el tema es recurrente:
www.meneame.net/search?q=algoritmo ordenacion
#36 #35 #7 #1 Además, el tema es recurrente:
www.meneame.net/search?q=algoritmo ordenacion
#35 #36 #37
¿Qué es recurrencia? -dices mientras clavas
en mi pupila tu pupila azul.
¿Qué es recurrencia? ¿Y tú me lo preguntas?
Recurrencia... eres tú.
#37 Hola, soy el caso base.
#1
#1 Lo que quiere decir es que ese día no había becarios...
#1 se llama tomy, y es el que trae los cafés y hace los curros aburridos, por eso le llamamos cariñosamente "la máquina automática encargada de la labor de ordenación"
#1 la de amazon
Lo que ya hacía cualquiera de vuestros abuelos que quisiera poner una baraja de cartas en orden.
Primero se separan por palos (oros, copas, ...) y después se ordenan por números e incluso se puede dividir en dos (del as al 5 y del 6 al rey) para agilizarlo aún más.
Estos informáticos deberían
jugar más a las cartashablar más con sus abuelos.#16 No está estudiado ni na el tema de la ordenación en informática
#16 No se por tu tierra pero entre los informáticos de Valencia se estila mucho el 'truc' y el poker
#27 Los que yo conocí eran más de Mus.
#28 Por eso digo los de Valencia... Ahora creo que toda la geografía ha sido conquistada po el LOL y WOW, ¿me equivoco?
#16 "y después se ordenan por números"
O sease, para ordenar las cartas, los que tu abuelos hacían era ordenar los números.
Ajá...
Es absurdo ordenarlos alfabéticamente. Se ordenan mediante un sistema decimal de clasificación.
#3 Ya, pero este vídeo no es sobre bibliotecas sino sobre algoritmos para ordenar los elementos de un vector.
Y tampoco habla sobre todos, hay muchos más.
https://en.wikipedia.org/wiki/Sorting_algorithm
#5 Titular: "La forma más rápida de ordenar alfabéticamente una librería" Entradilla: "Trabajas en la biblioteca de una universidad", "llega un cargamento de 1280 libros"... Como método de ordenación ya parte de una base errónea, la ordenación alfabética. Yo esperaría a que arreglaran la máquina esa de ordenar libros, que seguro que lo hace mejor. Más que una metáfora sobre librerías parece una fábula.
#6 Seguro que preferirías un vídeo que en lugar de la metáfora de la biblioteca se dedicara a explicar cómo ordenar cadenas de caracteres en un vector. Y si llegamos al heapsort o los árboles binarios pues mucho mejor.
#6 Es una metáfora sobre algoritmos de ordenamiento, y a mi me ha parecido muy muy clara. No hay que buscarle la puntilla a todo.
#6 En una palabra, burbuja... Jajajajaja nunca lo olvidaré, es uno de los primeros que aprendes.
En todos los algoritmos de ordenación hay cierta belleza,ingenio y sencillez.
#5 Me jode infinitamente que se llame vectores a los arrays. Un vector es un elemento de un espacio vectorial, hostias ya Pero parece que se ha quedado así y hay que aguantarse
Si Dewey levantara la cabeza...
¿La forma más rápida no era encargarle el trabajo al becario?
#2 Rápido Barato Bien Hecho.
Elige dos.
Se puede usar también la programación en paralelo. Se pide (por favor) a la gente de la biblioteca que agarre unos cuantos libros. Y en voz alta se exclama "amos a ver, quién tienen la A? quién tiene la B? quién tiene la C? etc...". Y en un ratito se ordenan los libros.
Bueno, en realidad es un poco más complicado
esta defasado este problema desaparecera ya dentro de poco con los PDF´s y epub´s y demas. por otra parte no me sirve para ordenar mis cosas en mi casa , al ser objetos completamente distintos, con distinto volumen , material o peso
#13 No, no esta desfasado, ordenar tus archivos se hace de la misma forma
#13 ¿Eres Drax?
¿Y que pasa con mergesort? También tiene muy buen coste
#44 Eso si tuviera una ayudante.
El método más rápido es comparar cada libro con su anterior comenzando por el segundo y si no está en orden arrojarlo a la chimenea. De esta manera ordenas en una sola pasada. ¡Chúpate esa Quicksort!
#40 Correcto. Creo que me he expresado mal...
#17 Eso estaba yo pensando, radix sort es el método que yo uso siempre que tengo que ordenar papeles a mano. De hecho, en según que casos es más eficiente que Quicksort (complejidad O(n*k) frente a O(n*log n)).
Sin ver el video... ¿Se nombra que recursos tienes? Si tienes un carrito y puedes ir buscando todos lo de la misma letra y luego aplicar el metodo que quieras avanzarias bastante; por ejemplo.
#4 Radix sort? https://es.wikipedia.org/wiki/Ordenamiento_Radix
#17 Obvio que se aplicaria un radix. No puedes cuantificar un titulo... ¿o si?
#24 Hombre, se puede asignar un valor a cada letra y leer el entero en una base no decimal. Luego ya está el tema de que hacer con el final de título y tal pero vamos, posible es.