¿Por qué se considera que mergesort es "el camino a seguir" cuando se ordenan listas y no se ordena de forma rápida? Escuché esto en una conferencia que vi en línea y la vi en un par de sitios web.¿Por qué es mejor el mergesort para listas enlazadas?
Una de las principales fuentes de eficiencia en quicksort es locality of reference, donde el hardware de la computadora está optimizado, por lo que acceder a ubicaciones de memoria cercanas es más rápido que acceder a ubicaciones de memoria dispersas en la memoria. El paso de particionamiento en quicksort generalmente tiene una localidad excelente, ya que accede a elementos de matriz consecutivos cerca del frente y la parte posterior. Como resultado, quicksort tiende a funcionar mucho mejor que otros algoritmos de clasificación como heapsort, aunque a menudo hace aproximadamente el mismo número de comparaciones y swaps, ya que en el caso de heapsort los accesos son más dispersos.
Además, el quicksort suele ser mucho más rápido que otros algoritmos de clasificación porque funciona in situ, sin necesidad de crear matrices auxiliares para contener valores temporales. En comparación con algo así como tipo de fusión, esto puede ser una gran ventaja porque el tiempo requerido para asignar y desasignar las matrices auxiliares puede ser notable. El funcionamiento in situ también mejora la localidad de quicksort.
Al trabajar con listas vinculadas, ninguna de estas ventajas se aplica necesariamente. Debido a que las celdas de la lista vinculada a menudo se encuentran dispersas en la memoria, no existe una bonificación de localidad para acceder a las celdas de la lista vinculada adyacente. En consecuencia, una de las enormes ventajas de rendimiento de quicksort se consume. Del mismo modo, los beneficios de trabajar en el lugar ya no se aplican, ya que el algoritmo de la lista enlazada de merge sort no necesita ningún espacio adicional de almacenamiento auxiliar.
Dicho esto, el quicksort sigue siendo muy rápido en las listas vinculadas. El tipo de combinación tiende a ser más rápido porque divide las listas de manera más pareja a la mitad y hace menos trabajo por iteración para realizar una fusión que para realizar el paso de creación de particiones.
Espero que esto ayude!
En la última línea del 3er párrafo, escribió "De forma similar, los beneficios de trabajar en el lugar ya no se aplican, ya que el algoritmo de la lista enlazada de merge sort no necesita ningún espacio adicional de almacenamiento auxiliar". ¿Por qué no necesita el espacio de almacenamiento auxiliar? – Geek
@Geek Probablemente debería haber dicho "el algoritmo de la lista enlazada de merge sort no necesita ** O (n) ** espacio de almacenamiento auxiliar." El algoritmo de fusión basado en arreglos estándar requiere que usted asigne espacio de almacenamiento adicional en el transcurso de la fusión porque los elementos deben moverse. En la ordenación por fusión con listas enlazadas, es posible mover elementos sin asignar una matriz externa simplemente volviéndolas a vincular. – templatetypedef
El costo de find() es más dañino para quicksort que mergesort.
Merge sort realiza más operaciones de "corto alcance" en los datos, por lo que es más adecuado para las listas vinculadas, mientras que la ordenación rápida funciona mejor con la estructura de datos de acceso aleatorio.
¿Qué quiere decir con 'find()'? – templatetypedef
Buscando entradas en la estructura de datos. Para un linst vinculado, siempre estás avanzando/retrocediendo, como tocar una cinta. –
No necesita usar la función de partición de acceso aleatorio utilizada en las matrices para quicksort en el caso de la lista vinculada. Puede particionar la lista enlazada haciendo una iteración en la lista y distribuyendo cada elemento en una de tres listas: una lista "menor que", una lista "mayor que" y una "lista igual", y luego recurrente en las dos últimas. Tiene razón en que la partición estándar es lenta, pero eso no hace que la lista enlazada sea lenta. – templatetypedef
mira esto http://stackoverflow.com/questions/497794/quicksort-slower-than-mergesort –