¿Por qué se prefiere la ordenación rápida para arrays y la ordenación combinada para listas vinculadas?

¿Por qué se prefiere Quick Sort para arreglos?

A continuación se muestran implementaciones recursivas e iterativas de Quick Sort y Merge Sort para arreglos.

Clasificación rápida recursiva para array.
Clasificación rápida iterativa para arrays.
Clasificación de combinación recursiva para arreglos
Clasificación de combinación iterativa para arreglos

• La ordenación rápida en su forma general es una ordenación en el lugar (es decir, no requiere ningún almacenamiento adicional) mientras que la ordenación por fusión requiere O(N) almacenamiento adicional, N denota el tamaño de la array que puede ser bastante costoso. La asignación y desasignación del espacio adicional utilizado para la ordenación por combinación aumenta el tiempo de ejecución del algoritmo.
• Al comparar la complejidad promedio, encontramos que ambos tipos de tipos tienen una complejidad promedio O (NlogN), pero las constantes difieren. Para arrays, la ordenación por fusión pierde debido al uso de espacio de almacenamiento O(N) adicional.
• La mayoría de las implementaciones prácticas de Quick Sort usan una versión aleatoria. La versión aleatoria tiene una complejidad de tiempo esperada de O (nLogn). El peor de los casos también es posible en la versión aleatoria, pero el peor de los casos no ocurre para un patrón en particular (como una array ordenada) y la ordenación rápida aleatoria funciona bien en la práctica.
• Quick Sort también es un algoritmo de clasificación compatible con caché, ya que tiene una buena localidad de referencia cuando se usa para arrays.
• Quick Sort también es recursivo de cola , por lo tanto, se realizan optimizaciones de llamada de cola.

¿Por qué se prefiere Merge Sort para las listas enlazadas?

A continuación se muestran las implementaciones de Quicksort y Mergesort para listas con enlaces simples y dobles.

Clasificación rápida para listas con enlaces dobles
Clasificación rápida para listas con enlaces simples
Clasificación por fusión para listas con enlaces simples
Clasificación por fusión para listas con enlaces dobles

• En el caso de las listas enlazadas, el caso es diferente principalmente debido a la diferencia en la asignación de memoria de las arrays y las listas enlazadas. A diferencia de las arrays, los Nodes de la lista enlazada pueden no estar adyacentes en la memoria.
• A diferencia de la array, en la lista enlazada , podemos insertar elementos en el medio en O (1) espacio adicional y O (1) tiempo si se nos da una referencia/puntero al Node anterior. Por lo tanto, la operación de combinación de clasificación por combinación se puede implementar sin espacio adicional para listas enlazadas.
• En arrays, podemos hacer acceso aleatorio ya que los elementos son continuos en la memoria. Digamos que tenemos una array A de enteros (4 bytes) y dejamos que la dirección de A[0] sea x, luego para acceder a A[i], podemos acceder directamente a la memoria en (x + i*4). A diferencia de las arrays, no podemos hacer acceso aleatorio en la lista enlazada.
• Quick Sort requiere mucho de este tipo de acceso. En la lista enlazada para acceder al i-ésimo índice, tenemos que viajar todos y cada uno de los Nodes desde el encabezado hasta el i-ésimo Node ya que no tenemos un bloque continuo de memoria. Por lo tanto, la sobrecarga aumenta para la ordenación rápida. Merge sort accede a los datos secuencialmente y la necesidad de acceso aleatorio es baja.

Artículos relacionados:

• ¿Por qué quicksort es mejor que mergesort?
• Conozca su algoritmo de clasificación | Conjunto 1 (Clasificación de armas utilizadas por lenguajes de programación)
• Clasificación de combinación iterativa
• Clasificación rápida iterativa

Gracias a Sayan Mukhopadhyay por proporcionar el borrador inicial del artículo anterior. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.