ipol: Consulta sobre ordenamiento clásico

En la guía para la tarea dice que debemos "Comparar la eficiencia con un arreglo simple para N ordenaciones sucesivas." y más adelante "comparar ciclos con ordenamiento clásico". No me queda muy claro a qué se refiere. Tenemos que implementar un método de ordenamiento clásico como el de burbuja y comparar con el heap? Si fuera así, el ordenamiento tipo burbuja deja los datos completamente ordenados, mientras que el heap no lo hace, por lo que la comparación no parece muy justa. Cuál es la idea en esta parte?

Gracias!

Saludos

Martín

Re: Consulta sobre ordenamiento clásico

de Matias Di Martino - viernes, 16 de mayo de 2014, 17:23

No se cual es la idea, pero interprete lo mismo que vos y pensaba comparar: ordenar a pedal con el heap. Si bien las comparaciones comparto que no son del todo justas me pensaba centrar en verificar que cada uno de los algoritmos es del orden que se supone que debería ser.

en fin... no te respondo nada pero bue

Re: Consulta sobre ordenamiento clásico

de Martin Rocamora - viernes, 16 de mayo de 2014, 20:14

Pero cuando dice "Comparación de ciclos de las dos implementaciones" se refiere solo a dos implementaciones, y entiendo que lo que hay que comparar es la implementación de la construcción del heap mediante inserciones sucesivas y la construcción eficiente (que está explicada en la wikipedia). Ahí la comparación tiene más sentido, porque son dos formas distintas de construir un heap.

Re: Consulta sobre ordenamiento clásico

de Juan Cardelino - viernes, 16 de mayo de 2014, 20:55

Si, está mal expresado en la letra. Eso es uno de los puntos.

Cuando hagamos el algoritmo de Dijkstra, haremos N iteraciones, y en cada una de ellas buscaremos un mínimo. En realidad el ordenamiento clásico debería haber dicho una búsqueda de mínimo. Por eso se pide una función find_minimum() que busca a pedal el mínimo en un array.

Si quieren tomen un poquito más de tiempo, para hacerlo más tranquilos.

Re: Consulta sobre ordenamiento clásico

de Martin Rocamora - viernes, 16 de mayo de 2014, 21:44

OK. Entiendo. Hay que comparar el costo de obtener el mínimo con búsqueda a pedal en un arreglo, frente extraer el primer elemento del heap (es decir O(1) frente a O(n)).

Otra comparación que es interesante es la del costo de construcción con los diferentes métodos. A mi me está dando que la manera ineficiente (inserción sucesiva de elementos) en lugar de ser O(n log n), en realidad es O(n). Esto parece ser porque la estimación O(n log n), que considera costo de inserción O(log n) y n operaciones es de peor caso, pero en realidad el costo promedio de una inserción es O(1) (como está en las transparencias de clase) con lo que la construcción es de costo O(n). La implementación eficiente también es O(n) y solo difieren en la constante que determina la pendiente del crecimiento lineal con los datos. Por suerte la implementación eficiente está un poco por debajo.

Saludos y gracias!