Clasificación rápida frente a clasificación combinada

Quick sort es un algoritmo interno que se basa en la estrategia divide y vencerás. En esto:

• La array de elementos se divide en partes repetidamente hasta que ya no es posible dividirla más.
• También se conoce como «clasificación de intercambio de partición» .
• Utiliza un elemento clave (pivote) para particionar los elementos.
• Una partición izquierda contiene todos aquellos elementos que son más pequeños que el pivote y una partición derecha contiene todos aquellos elementos que son mayores que el elemento clave.

Merge sort es un algoritmo externo y se basa en la estrategia divide y vencerás. En esto:

• Los elementos se dividen en dos subarreglos (n/2) una y otra vez hasta que solo queda un elemento.
• La ordenación por combinación utiliza almacenamiento adicional para ordenar la array auxiliar.
• La ordenación por combinación usa tres arreglos donde dos se usan para almacenar cada mitad, y el tercero externo se usa para almacenar la lista ordenada final al fusionar otros dos y luego cada arreglo se ordena recursivamente.
• Por último, todos los subconjuntos se fusionan para convertirlo en un tamaño de elemento ‘n’ del conjunto.

Clasificación rápida frente a clasificación combinada

1. Partición de elementos en la array :
   en la ordenación por fusión, la array se divide en solo 2 mitades (es decir, n/2).
   mientras que
   en caso de clasificación rápida, la array se divide en cualquier proporción. No existe la obligación de dividir la array de elementos en partes iguales en clasificación rápida.
2. Complejidad del peor de los casos :
   la complejidad del peor de los casos de clasificación rápida es O (n2) ya que se necesitan muchas comparaciones en las peores condiciones.
   mientras que
   en la ordenación por fusión, el peor de los casos y el caso promedio tienen las mismas complejidades O (n log n).
3. Uso con conjuntos de datos :
   la ordenación por combinación puede funcionar bien en cualquier tipo de conjuntos de datos, independientemente de su tamaño (ya sea grande o pequeño).
   mientras que
   la ordenación rápida no puede funcionar bien con grandes conjuntos de datos.
4. Requisito de espacio de almacenamiento adicional : la
   ordenación por combinación no está en su lugar porque requiere espacio de memoria adicional para almacenar las arrays auxiliares.
   mientras que
   la clasificación rápida está en su lugar, ya que no requiere ningún almacenamiento adicional.
5. Eficiencia : la
   ordenación por combinación es más eficiente y funciona más rápido que la ordenación rápida en el caso de conjuntos de datos o tamaños de array más grandes.
   mientras que
   la ordenación rápida es más eficiente y funciona más rápido que la ordenación combinada en el caso de conjuntos de datos o tamaños de array más pequeños.
6. Método de clasificación :
   la clasificación rápida es un método de clasificación interno en el que los datos se clasifican en la memoria principal.
   mientras que
   la clasificación por combinación es un método de clasificación externo en el que los datos que se van a clasificar no se pueden acomodar en la memoria y necesitan memoria auxiliar para la clasificación.
7. Estabilidad :
   la ordenación por combinación es estable ya que dos elementos con el mismo valor aparecen en el mismo orden en la salida ordenada que en la array no ordenada de entrada.
   mientras que
   Quick sort es inestable en este escenario. Pero se puede hacer estable usando algunos cambios en el código.
8. Preferido para :
   se prefiere la ordenación rápida para arrays.
   mientras que
   Merge sort es preferible para listas enlazadas.
9. Localidad de referencia :
   Quicksort exhibe una buena localidad de caché y esto hace que quicksort sea más rápido que merge sort (en muchos casos, como en un entorno de memoria virtual).

Base de comparación	Ordenación rápida	Ordenar por fusión
La partición de elementos en la array.	La división de una array de elementos se realiza en cualquier proporción, no necesariamente dividida por la mitad.	En el ordenamiento por fusión, la array se divide en solo 2 mitades (es decir, n/2).
Complejidad en el peor de los casos	En 2)	O (iniciar sesión)
funciona bien en	Funciona bien en una array más pequeña.	Funciona bien en cualquier tamaño de array
Velocidad de ejecución	Funciona más rápido que otros algoritmos de clasificación para conjuntos de datos pequeños como la clasificación por selección, etc.	Tiene una velocidad constante en cualquier tamaño de datos.
Requisito de espacio de almacenamiento adicional	Menos (en el lugar)	Más (no en el lugar)
Eficiencia	Ineficiente para arreglos más grandes	Más eficiente
método de clasificación	Interno	Externo
Estabilidad	No es estable	Estable
Preferido para	para arreglos	para listas enlazadas
Localidad de referencia	bueno	pobre