Tenemos 14 objetos, de pesos indeterminados.También tenemos una balanza de dos platillos, con la cual podemos comparar cualquier par de objetos o grupos de objetos, y saber cuál objeto o grupo es el que pesa más.
Queremos ordenar los objetos por peso, y para ello queremos usar la menor cantidad posible de pesadas.
¿Cómo hacerlo?
7 comentarios:
¿Utilizando Quicksort o algún otro algoritmo de ordenamiento?
¿o hay alguna trampa en el hecho de que sean 14?
QuickSort es un buen algoritmo cuando se permite comparar solamente un par de objetos cada vez; pero sospecho que usando el agrupamiento de objetos en los platillos se puede optimizar bastante.
mmmh. Lo voy a pensar, pero a primera vista, me parece que la posibilidad de que dos grupos pesen lo mismo termina empeorando la cantidad de pesadas
MergeSort te asegura un tiempo razonable (n·log(n)). Con QuickSort (a menos que seas muy cuidadoso) puedes tener tiempos del orden de n².
Pero mi favorito es, con diferencia, el HeapSort. Es taaaan retorcido que no puedo dejar de maravillarme con él.
No creo que agrupar objetos sea de mucha utilidad si se trata de ordenarlos todos. Sería más sencillo y útil en el caso de que todos los elementos fuesen iguales menos uno. Y quizá también sea de utilidad si aseguras que los pesos están en un determinado rango o que son todos diferentes (por ejemplo 1kg, 2kg, 3kg, ... 14kg).
Gracias Carlos por la info. Ya curiosearé el HeapSort.
De todas formas no puedo dejar de pensar que en algo debería ayudar el hecho de poder agrupar los objetos.
Imaginate una computadora una de cuyas capacidades es sumar un conjunto de números en tiempo constante; ¿no diseñarías algoritmos que aprovecharan esa característica? Tal vez no de ordenamiento, pero quizá para otras aplicaciones...
Sí, pero en este caso no nos ayuda.
Sumando objetos en tiempo constante puedes encontrar el máximo (o el mínimo) de un conjunto de objetos en tiempo logarítmico en vez de lineal. Eso significa que puedes implementar una cola de prioridad en cualquier vector sin necesidad de un tratamiento previo y sin necesidad de complicarte la vida.
Lamentablemente eso no ayuda a ordenar objetos porque, por ejemplo, si usas SelectionSort y ordenas tus elementos eligiendo el más grande, luego el más grande de los que queda y así hasta agotarlos creo que no ganas demasiado.
Sin ir más lejos HeapSort hace exactametne eso: montar una cola de prioridad con un Heap sobre el mismo vector y luego hacer SelectionSort usando esa cola n veces para tardar n*log(n) en ordenarlo. En esta nueva situación te ahorras la parte de montar el Heap y estoy seguro de que mejoras mucho la constante de implementación pero no sé si puedes mejorar el tiempo asintótico.
Aunque quizá por esa vía, por la de montar una cola de prioridad ULTRA-eficiente puedas mejorar el tiempo de encontrar el mínimo/máximo de la cola de prioridad y lograr una ordenación en tiempo n*log(log(n)). Pero desde luego no será un algoritmo evidente :-)
Lo mío es menos erudito.
Hice algunas pruebas con cantidades pequeñas con valores consecutivos y con valores medio al azar y no encontré ninguna manera de mejorar un ordenamiento tradicional (más bien al contrario)
No descarto que con cantidades grandes de datos tal vez se obtenga una mejora... pero no se me ocurre como.
Publicar un comentario