Ambas técnicas de clasificación, clasificación rápida y clasificación de fusión se basan en el método de dividir y conquistar, en el que el conjunto de elementos se divide 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 combinación para ordenar un gran conjunto de elementos.
Gráfica comparativa
| Bases para la comparación | Ordenación rápida | Fusionar orden |
|---|---|---|
| Particionamiento de los elementos en la matriz. | La división de una lista de elementos no necesariamente se divide en la mitad. | La matriz siempre se divide en la mitad (n / 2). |
| Peor complejidad del caso | En 2) | 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 pequeños conjuntos de datos. | Velocidad consistente en todo tipo de conjuntos de datos. |
| Requisito de espacio de almacenamiento adicional | 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
La clasificación rápida se utiliza de forma generalizada en el algoritmo de clasificación, ya que es rápido para las matrices cortas. El conjunto de los elementos se divide en partes repetidamente hasta que no es posible dividirlo más. La ordenación rápida también se conoce como ordenación de intercambio de particiones . Utiliza un elemento clave (conocido como el 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 de forma recursiva.
Supongamos que A es una matriz A [1], A [2], A [3], …… .., A [n] de n números que deben ser ordenados. El algoritmo de clasificación rápida se compone de los siguientes pasos.
- El primer elemento o cualquier elemento aleatorio seleccionado como clave, asume clave = A (1).
- El puntero "bajo" se coloca en la segunda posición y el puntero "arriba" se coloca en el último elemento de la matriz, es decir, bajo = 2 y arriba = n;
- Consistentemente, incremente el puntero "bajo" en una posición hasta que aparezca la tecla (A [bajo]>).
- Constantemente, disminuya el puntero "arriba" en una posición hasta que (A [arriba] <= tecla).
- Si up es mayor que low, el intercambio A [low] con A [up].
- Repita los pasos 3, 4 y 5 hasta que la condición en el paso 5 falle (es decir, subiendo <= bajo) y luego intercambie A [arriba] con la tecla.
- 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 subarreglos.
- El procedimiento anterior se aplica repetidamente a los subarreglos hasta que se ordena la matriz completa.
Ventajas y desventajas
Posee un buen comportamiento promedio de los casos. La complejidad del tiempo de ejecución de la ordenación rápida es buena, ya que es más rápida que los algoritmos como la ordenación por burbuja, la ordenación por inserción y la ordenación por selección. Sin embargo, es complejo y muy recursivo, por lo que no es adecuado para arreglos grandes.
Definición de Merge Sort
La clasificación de fusión es un algoritmo externo que también se basa en la estrategia de dividir y conquistar. Los elementos se dividen en subarreglas (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 clasificación de fusión utiliza tres matrices, donde se utilizan dos para almacenar cada mitad, y la tercera se utiliza para almacenar la lista ordenada final. Cada matriz se clasifica de forma recursiva. Finalmente, las subarrays se fusionan para hacer que sea 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.
Sea A la matriz de n número de elementos a clasificar A [1], A [2], ………, A [n]. La ordenación de fusión sigue los pasos dados.
- Divida la matriz A en aproximadamente n / 2 sub-matriz ordenada por 2, lo que significa que los elementos en (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]), (A [n-1], A [n]) los subconjuntos deben estar ordenados.
- Combine cada par de pares para obtener la lista de subgrupos ordenados de tamaño 4; los elementos de los subarrays también están ordenados, (A [1], A [2], A [3], A [4]), ……, (A [k-1], A [k], A [k + 1], A [k + 2]), ……., (A [n-3], A [n-2], A [n-1], A [n]).
- El paso 2 se realiza repetidamente hasta que solo hay una matriz ordenada de tamaño n.
Ventajas y desventajas
El algoritmo de ordenamiento de fusión se realiza de la misma manera y precisión, independientemente del número de elementos involucrados en la clasificación. Funciona bien incluso con el gran conjunto de datos. Sin embargo, consume gran parte de la memoria.
Diferencias clave entre la ordenación rápida y la ordenación por fusión
- En la ordenación de combinación, la matriz debe dividirse en solo dos mitades (es decir, n / 2). A diferencia de, en orden rápido, no hay obligación de dividir la lista en elementos iguales.
- El peor caso de complejidad de la clasificación rápida es O (n2), ya que se necesitan muchas más comparaciones en las peores condiciones. En contraste, la ordenación de mezcla tiene las mismas complejidades de caso y promedio, es decir O (n log n).
- La clasificación de fusión puede funcionar bien en cualquier tipo de conjuntos de datos, ya sean grandes o pequeños. Por el contrario, la ordenación rápida no puede funcionar bien con grandes conjuntos de datos.
- 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.
- La ordenación de mezcla requiere espacio de memoria adicional para almacenar los arreglos auxiliares. Por otro lado, la clasificación rápida no requiere mucho espacio para almacenamiento adicional.
- La ordenación por fusión es más eficiente que la ordenación rápida.
- La clasificación rápida es un método de clasificación interno en el que los datos que se deben clasificar se ajustan a la vez en la memoria principal. A la inversa, la clasificación de combinación es un método de clasificación externo en el que los datos que se deben clasificar no se pueden acomodar en la memoria al mismo tiempo y algunos deben mantenerse en la memoria auxiliar.
Conclusión
La clasificació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 clasificación de combinación. Aunque la ordenación de mezcla 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 (registro n).
