Contenido

• Cuadro comparativo
• Definición de ordenación rápida
• Definición de orden de fusión
• Conclusión

Los algoritmos de ordenación rápida y fusión se basan en el algoritmo de división y conquista que funciona de manera bastante similar. La diferencia previa entre la ordenación rápida y la fusión es que en la ordenación rápida el elemento pivote se usa para la ordenación. Por otro lado, la ordenación por fusión no utiliza el elemento pivote para realizar la ordenación.

Ambas técnicas de clasificación, clasificación rápida y combinación se basan en el método de división y conquista en el que el conjunto de elementos se separa y luego se combina después de la reorganización. La ordenación rápida generalmente requiere más comparaciones que la ordenación por fusión para ordenar un gran conjunto de elementos.

1. 1. Cuadro comparativo
   2. Definición
   3. Diferencias clave
   4. Conclusión

Cuadro comparativo

Bases para la comparación	Ordenación rápida	Ordenar fusión
Particionamiento de los elementos en la matriz	La división de una lista de elementos no se divide necesariamente a la mitad.	La matriz siempre se divide en la mitad (n / 2).
La peor complejidad del caso	En2)	O (n log n)
Funciona bien en	Matriz más pequeña	Funciona bien en cualquier tipo de matriz.
Velocidad	Más rápido que otros algoritmos de clasificación para conjuntos de datos pequeños.	Velocidad constante en todo tipo de conjuntos de datos.
Requisito adicional de espacio de almacenamiento	Menos	Más
Eficiencia	Ineficiente para matrices más grandes.	Más eficiente.
Método de clasificación	Interno	Externo

Definición de ordenación rápida

Ordenación rápida se usa de forma generalizada como algoritmo de clasificación, ya que es rápido para las matrices cortas. El conjunto de elementos se divide en partes repetidamente hasta que no es posible dividirlo más. La ordenación rápida también se conoce como tipo de intercambio de partición. Utiliza un elemento clave (conocido como pivote) para particionar los elementos. Una partición contiene aquellos elementos que son más pequeños que el elemento clave. Otra partición contiene aquellos elementos que son mayores que el elemento clave. Los elementos se ordenan recursivamente.

Supongamos que A es una matriz A, A, A, …… .., A de n número que debe clasificarse. El algoritmo de ordenación rápida consta de los siguientes pasos.

1. El primer elemento o cualquier elemento aleatorio seleccionado como clave, suponga clave = A (1).
2. El puntero "bajo" se coloca en el segundo y el puntero "arriba" se coloca en el último elemento de la matriz, es decir, bajo = 2 y arriba = n;
3. Constantemente, incremente el puntero "bajo" en una posición hasta que (tecla A>).
4. Constantemente, disminuya el puntero "arriba" en una posición hasta (tecla A <=).
5. Si arriba es mayor que el intercambio bajo A con A.
6. Repita los pasos 3,4 y 5 hasta que falle la condición en el paso 5 (es decir, arriba <= bajo), luego intercambie A con la tecla.
7. Si los elementos a la izquierda de la clave son más pequeños que la clave y los elementos a la derecha de la clave son mayores que la clave, la matriz se divide en dos sub-matrices.
8. El procedimiento anterior se aplica repetidamente a las submatrices hasta que se ordena toda la matriz.

   

   
   

Ventajas y desventajas

Posee un buen comportamiento promedio de casos. La complejidad del tiempo de ejecución del ordenamiento rápido es buena, es más rápido que los algoritmos como el ordenamiento por burbuja, el ordenamiento por inserción y el ordenamiento por selección. Sin embargo, es complejo y muy recursivo, esa es la razón por la que no es adecuado para matrices grandes.

Definición de orden de fusión

Ordenar fusión es un algoritmo externo que también se basa en la estrategia de dividir y conquistar. Los elementos se dividen en sub-matrices (n / 2) una y otra vez hasta que solo queda un elemento, lo que disminuye significativamente el tiempo de clasificación. Utiliza almacenamiento adicional para almacenar la matriz auxiliar. La ordenación por fusión usa tres matrices donde dos se usan para almacenar cada mitad, y la tercera se usa para almacenar la lista ordenada final. Cada matriz se ordena recursivamente. Finalmente, las submatrices se fusionan para convertirlo en un tamaño de elemento de la matriz. La lista siempre se divide en solo la mitad (n / 2) diferente a la ordenación rápida.

Deje A ser la matriz de n número de elementos que se ordenarán A, A, ………, A. La clasificación de fusión sigue los pasos dados.

1. Dividir el conjunto A en aproximadamente n / 2 subconjuntos ordenados por 2, lo que significa que los elementos en los subconjuntos (A, A), (A, A), (A, A), (A, A) deben Estar en orden.
2. Combine cada par de pares para obtener la lista de subarreglos ordenados de tamaño 4; los elementos en las submatrices también están ordenados, (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. El paso 2 se realiza repetidamente hasta que solo haya una matriz ordenada de tamaño n.

   

Ventajas y desventajas

El algoritmo de ordenamiento por fusión funciona exactamente de la misma manera y sin importar la cantidad de elementos involucrados en el ordenamiento. Funciona bien incluso con el gran conjunto de datos. Sin embargo, consume una mayor parte de la memoria.

1. En el orden de fusión, la matriz debe dividirse en solo dos mitades (es decir, n / 2). Por el contrario, en forma rápida, no hay obligación de dividir la lista en elementos iguales.
2. El peor de los casos de complejidad de la clasificación rápida es O (n²) ya que requiere muchas más comparaciones en las peores condiciones. Por el contrario, los tipos de combinación tienen las mismas complejidades de caso peor y de caso promedio, es decir, O (n log n).
3. La ordenación por fusión puede funcionar bien en cualquier tipo de conjuntos de datos, ya sea grande o pequeño. Por el contrario, la ordenación rápida no puede funcionar bien con grandes conjuntos de datos.
4. La ordenación rápida es más rápida que la ordenación por fusión en algunos casos, como para conjuntos de datos pequeños.
5. La ordenación por fusión requiere espacio de memoria adicional para almacenar las matrices auxiliares. Por otro lado, la clasificación rápida no requiere mucho espacio para almacenamiento adicional.
6. La ordenación por fusión es más eficiente que la ordenación rápida.
7. La ordenación rápida es un método de ordenación interno donde los datos que se ordenarán se ajustan a la vez en la memoria principal. Por el contrario, la ordenación por fusión es un método de ordenación externo en el que los datos que se van a ordenar no se pueden acomodar en la memoria al mismo tiempo y algunos deben mantenerse en la memoria auxiliar.

Conclusión

La ordenación rápida es casos más rápidos pero es ineficiente en algunas situaciones y también realiza muchas comparaciones en comparación con la ordenación por fusión. Aunque la ordenación por fusión requiere menos comparación, necesita un espacio de memoria adicional de 0 (n) para almacenar la matriz adicional, mientras que la ordenación rápida necesita espacio de O (log n).