¿Cuál es la diferencia entre Quicksort y Merge Sort
Share
los diferencia principal entre la ordenación rápida y la combinación es que la quicksort ordena los elementos comparando cada elemento con un elemento llamado pivote, mientras que la ordenación por fusión divide la matriz en dos subarrays una y otra vez hasta que queda un elemento.
La clasificación es el método de organizar los datos en un orden particular. Al organizar los datos, es posible considerar el orden numérico o lexicográfico. La clasificación ayuda a buscar y acceder a los elementos de datos más rápido y más rápido. Hay varios algoritmos de clasificación, y Quicksort y Merge Sort son dos de ellos..
Áreas clave cubiertas
1. Qué es Quicksort
- Definición, Funcionalidad
2. ¿Qué es la clasificación por fusión?
- Definición, Funcionalidad
3. ¿Cuál es la diferencia entre Quicksort y Merge Sort
- Comparación de diferencias clave
Términos clave
Algoritmo, Array, Fusionar Ordenar, Quicksort
Qué es Quicksort
Quicksort es un algoritmo interno que utiliza la técnica de "divide y vencerás". También es llamado un tipo de intercambio de particiones. Utiliza un elemento clave llamado pivote para comparar y particionar los elementos de la matriz. Los elementos con un valor menor que el pivote van al lado izquierdo del pivote, mientras que los elementos con un valor mayor que el pivote van al lado derecho del pivote. La sección izquierda se llama la partición izquierda, y la sección derecha se llama la partición derecha.
Figura 1: Quicksort
Consulte el siguiente ejemplo.
36 34 43 11 15 20 28 45 27 32
Considere 32 como el pivote y considere 36 y 27. Las condiciones 36 < pivot, 27 > Los pivotes son falsos. Por lo tanto, podemos intercambiar estos dos valores. Ahora la lista es la siguiente.
27 34 43 11 15 20 28 45 36 32
Considera los valores 34 y 45. Al considerar 34 < pivot, the condition is false. Similarly, 45 > La condición de pivote es verdadera. Ahora, podemos pasar de 45 a 28. Consideremos 34 y 28. 34 < pivot is false and 28 > el pivote es falso Por lo tanto, podemos intercambiar 34 y 28..
27 28 43 11 15 20 34 45 36 32
Considera 43 y 20. 43 < pivot is false. 20 > el pivote es falso Por lo tanto, podemos intercambiar los dos números. Ahora la lista es la siguiente.
27 28 20 11 15 43 34 45 36 32
Ahora considera 11 y 15. 11 < pivot is true. We can consider 15. It is less than 32. It is the overlapping point, and we can place 32 as follows.
27 28 20 11 15 32 43 34 45 36
Ahora los números en el lado izquierdo del pivote son más pequeños que el pivote, y el lado derecho del pivote es mayor que el pivote. Podemos aplicar quicksort a las particiones izquierda y derecha para ordenar la lista completa.
¿Qué es la clasificación por fusión?
La clasificación de fusión es un algoritmo externo que utiliza la técnica de "divide y vencerás". Se divide la matriz en dos secciones. Ordena cada matriz y las combina para formar la matriz ordenada. La ordenación de mezcla requiere almacenamiento adicional para ordenar la matriz auxiliar.
Considera el siguiente ejemplo.
Figura 2: Combinar clasificación
Podemos dividir la matriz en dos secciones. Ahora hay dos matrices de la siguiente manera.
38 27 43 3 9 82 10
Considere 38 27 43 3. Podemos dividirlo en dos matrices nuevamente. Son 38 27 y 43 3. 38 27 se divide en 38 y 27, mientras que 43 3 se divide en 43 y 3. La clasificación 38 y 27 da 27 38. La clasificación 43 3 da 3 43. Ahora es posible combinar 27 38 y 3 43 Después de clasificarlos, obtenemos una matriz como 3 27 38 43.
Del mismo modo, considere 9 82 10. Podemos dividirlo en dos matrices nuevamente. Son 9 82 y 10. 9 82 se divide en 9 y 82. Además, hay el número 10 en la otra matriz. 9 y 82 se clasifican como 9 82. Por lo tanto, esta matriz y la matriz con valor 10 combinan y proporcionan 9 10 y 82.
Finalmente, 3 27 38 43 y 9 10 82 se combinan para proporcionar la matriz ordenada.
Diferencia entre Quicksort y Merge Sort
Definición
Quicksort es un algoritmo de clasificación eficiente, que sirve como un método sistemático para colocar los elementos de una matriz en orden. En contraste, la ordenación de mezcla es un algoritmo de ordenación eficiente, de propósito general y basado en comparación. Por lo tanto, esta es la diferencia fundamental entre quicksort y merge sort.
Funcionalidad
Sobre todo, la funcionalidad es la principal diferencia entre la ordenación rápida y la ordenación por fusión. Quicksort ordena los elementos comparando cada elemento con el pivote, mientras que la ordenación por fusión divide la matriz en dos subarrays (n / 2) una y otra vez hasta que queda un elemento.
Solicitud
Además, si bien quicksort es adecuado para matrices pequeñas, la ordenación por fusión funciona para cualquier tipo de matriz.
Velocidad
Otra diferencia entre la ordenación rápida y combinación es que la ordenación rápida funciona más rápido para conjuntos de datos pequeños, mientras que la ordenación combinada funciona a una velocidad constante para todos los conjuntos de datos.
Requerimiento de espacio
Por otra parte, el requisito de espacio también es una diferencia importante entre la ordenación rápida y la combinación. Quicksort requiere un espacio mínimo en comparación con la ordenación de combinación.
Eficiencia
Además, quicksort no es eficiente para arreglos grandes, pero la ordenación por fusión es más eficiente que quicksort. Por lo tanto, esta es otra diferencia entre el ordenamiento rápido y el ordenamiento por fusión.
Conclusión
En resumen, la principal diferencia entre la ordenación rápida y combinación es que la ordenación rápida ordena los elementos comparando cada elemento con un elemento llamado pivote, mientras que la clasificación combinada divide la matriz en dos subarrays una y otra vez hasta que queda un elemento.
Referencia:
1. Algoritmo de ordenación rápida | Parte 2, Educación 4u, 15 de marzo de 2018, disponible aquí.
2. Ejemplo de Combinación, Educación 4u, 15 de marzo de 2018, disponible aquí.
Imagen de cortesía:
1. “Quicksort-diagram” por Znupi - Trabajo propio (Dominio público) a través de Commons Wikimedia
2. "Combinar diagrama de algoritmo de clasificación" Por Vineet Kumar en la Wikipedia en inglés - Transferido de en.wikipedia a Commons por Eric Bauman usando CommonsHelper (Dominio público) a través de Commons Wikimedia
